硬件故障

Hardware Faults

当我们想到系统故障的原因时，我们很快就会想到硬件故障。硬盘崩溃、内存故障、电网停电、有人拔错网线。任何使用过大型数据中心的人都可以告诉您，当您拥有大量机器时，这些事情总是会发生。

When we think of causes of system failure, hardware faults quickly come to mind. Hard disks crash, RAM becomes faulty, the power grid has a blackout, someone unplugs the wrong network cable. Anyone who has worked with large datacenters can tell you that these things happen all the time when you have a lot of machines.

据报道，硬盘的平均无故障时间 (MTTF) 约为 10 至 50 年 [ 5 , 6 ]。因此，在拥有 10,000 个磁盘的存储集群上，我们预计平均每天会有一个磁盘死亡。

Hard disks are reported as having a mean time to failure (MTTF) of about 10 to 50 years [5, 6]. Thus, on a storage cluster with 10,000 disks, we should expect on average one disk to die per day.

我们的第一反应通常是为各个硬件组件添加冗余，以降低系统的故障率。磁盘可以设置为 RAID 配置，服务器可以具有双电源和可热插拔 CPU，数据中心可以具有电池和柴油发电机作为备用电源。当一个组件失效时，多余的组件可以取代它，同时更换损坏的组件。这种方法不能完全防止硬件问题导致故障，但它很好理解，并且通常可以使机器不间断地运行数年。

Our first response is usually to add redundancy to the individual hardware components in order to reduce the failure rate of the system. Disks may be set up in a RAID configuration, servers may have dual power supplies and hot-swappable CPUs, and datacenters may have batteries and diesel generators for backup power. When one component dies, the redundant component can take its place while the broken component is replaced. This approach cannot completely prevent hardware problems from causing failures, but it is well understood and can often keep a machine running uninterrupted for years.

直到最近，硬件组件的冗余对于大多数应用程序来说已经足够了，因为它使得单台机器完全故障的情况相当罕见。只要您可以相当快地将备份恢复到新计算机上，在大多数应用程序中，发生故障时的停机时间就不会是灾难性的。因此，只有少数应用程序需要多机冗余，而高可用性对于这些应用程序来说是绝对必要的。

Until recently, redundancy of hardware components was sufficient for most applications, since it makes total failure of a single machine fairly rare. As long as you can restore a backup onto a new machine fairly quickly, the downtime in case of failure is not catastrophic in most applications. Thus, multi-machine redundancy was only required by a small number of applications for which high availability was absolutely essential.

然而，随着数据量和应用程序计算需求的增加，更多的应用程序开始使用更多数量的机器，这相应地增加了硬件故障率。此外，在 Amazon Web Services (AWS) 等一些云平台中，虚拟机实例在没有警告的情况下变得不可用是相当常见的[ 7 ]，因为这些平台的设计优先考虑灵活性和弹性^而 不是单机可靠性。

However, as data volumes and applications’ computing demands have increased, more applications have begun using larger numbers of machines, which proportionally increases the rate of hardware faults. Moreover, in some cloud platforms such as Amazon Web Services (AWS) it is fairly common for virtual machine instances to become unavailable without warning [7], as the platforms are designed to prioritize flexibility and elasticityⁱ over single-machine reliability.

因此，通过优先使用软件容错技术或在硬件冗余之外使用软件容错技术，出现了一种可以容忍整个机器丢失的系统的趋势。此类系统还具有操作优势：如果需要重新启动计算机（例如，应用操作系统安全补丁），单服务器系统需要计划停机时间，而可以容忍机器故障的系统可以一次对一个节点进行修补，整个系统不会停机（滚动升级；请参阅第 4 章）。

Hence there is a move toward systems that can tolerate the loss of entire machines, by using software fault-tolerance techniques in preference or in addition to hardware redundancy. Such systems also have operational advantages: a single-server system requires planned downtime if you need to reboot the machine (to apply operating system security patches, for example), whereas a system that can tolerate machine failure can be patched one node at a time, without downtime of the entire system (a rolling upgrade; see Chapter 4).

软件错误

Software Errors

我们通常认为硬件故障是随机的且相互独立的：一台机器的磁盘发生故障并不意味着另一台机器的磁盘也会发生故障。可能存在弱相关性（例如由于共同原因，例如服务器机架中的温度），但否则大量硬件组件不太可能同时发生故障。

We usually think of hardware faults as being random and independent from each other: one machine’s disk failing does not imply that another machine’s disk is going to fail. There may be weak correlations (for example due to a common cause, such as the temperature in the server rack), but otherwise it is unlikely that a large number of hardware components will fail at the same time.

另一类故障是系统内的系统错误[ 8 ]。此类故障更难以预测，并且由于它们在节点之间相关，因此它们往往会比不相关的硬件故障导致更多的系统故障[ 5 ]。示例包括：

Another class of fault is a systematic error within the system [8]. Such faults are harder to anticipate, and because they are correlated across nodes, they tend to cause many more system failures than uncorrelated hardware faults [5]. Examples include:

• 一种软件错误，当输入特定的错误输入时，该错误会导致应用程序服务器的每个实例崩溃。例如，考虑 2012 年 6 月 30 日的闰秒，由于 Linux 内核中的错误，导致许多应用程序同时挂起 [ 9 ]。

• A software bug that causes every instance of an application server to crash when given a particular bad input. For example, consider the leap second on June 30, 2012, that caused many applications to hang simultaneously due to a bug in the Linux kernel [9].

• 耗尽某些共享资源（CPU 时间、内存、磁盘空间或网络带宽）的失控进程。

• A runaway process that uses up some shared resource—CPU time, memory, disk space, or network bandwidth.

• 系统所依赖的服务速度减慢、变得无响应或开始返回损坏的响应。

• A service that the system depends on that slows down, becomes unresponsive, or starts returning corrupted responses.

• 级联故障，其中一个组件中的小故障触发另一个组件中的故障，进而触发更多故障[ 10 ]。

• Cascading failures, where a small fault in one component triggers a fault in another component, which in turn triggers further faults [10].

导致此类软件故障的错误通常会潜伏很长一段时间，直到由一组不寻常的情况触发。在这些情况下，我们发现软件正在对其环境做出某种假设——虽然这种假设通常是正确的，但由于某种原因它最终不再正确[11 ]。

The bugs that cause these kinds of software faults often lie dormant for a long time until they are triggered by an unusual set of circumstances. In those circumstances, it is revealed that the software is making some kind of assumption about its environment—and while that assumption is usually true, it eventually stops being true for some reason [11].

软件中的系统故障问题没有快速的解决方案。许多小事情都可以提供帮助：仔细思考系统中的假设和交互；彻底的测试；进程隔离；允许进程崩溃并重新启动；测量、监控和分析生产中的系统行为。如果系统期望提供某种保证（例如，在消息队列中，传入消息的数量等于传出消息的数量），则它可以在运行时不断检查自身，并在发现差异时发出警报[ 12 ]。

There is no quick solution to the problem of systematic faults in software. Lots of small things can help: carefully thinking about assumptions and interactions in the system; thorough testing; process isolation; allowing processes to crash and restart; measuring, monitoring, and analyzing system behavior in production. If a system is expected to provide some guarantee (for example, in a message queue, that the number of incoming messages equals the number of outgoing messages), it can constantly check itself while it is running and raise an alert if a discrepancy is found [12].

人为错误

Human Errors

人类设计和构建软件系统，维持系统运行的操作人员也是人类。即使他们有最好的意图，人类也被认为是不可靠的。例如，一项针对大型互联网服务的研究发现，运营商的配置错误是中断的主要原因，而硬件故障（服务器或网络）仅在 10-25% 的中断中发挥了作用 [13 ]。

Humans design and build software systems, and the operators who keep the systems running are also human. Even when they have the best intentions, humans are known to be unreliable. For example, one study of large internet services found that configuration errors by operators were the leading cause of outages, whereas hardware faults (servers or network) played a role in only 10–25% of outages [13].

尽管人类不可靠，我们如何使我们的系统可靠？最好的系统结合了多种方法：

How do we make our systems reliable, in spite of unreliable humans? The best systems combine several approaches:

• 以尽量减少出错机会的方式设计系统。例如，精心设计的抽象、API 和管理界面可以轻松地做“正确的事情”并阻止“错误的事情”。然而，如果接口限制太多，人们就会绕过它们，从而抵消它们的好处，所以这是一个很难实现的平衡。

• Design systems in a way that minimizes opportunities for error. For example, well-designed abstractions, APIs, and admin interfaces make it easy to do “the right thing” and discourage “the wrong thing.” However, if the interfaces are too restrictive people will work around them, negating their benefit, so this is a tricky balance to get right.

• 将人们最容易犯错误的地方与可能导致失败的地方分开。特别是，提供功能齐全的非生产沙箱环境，人们可以在其中使用真实数据安全地探索和实验，而不会影响真实用户。

• Decouple the places where people make the most mistakes from the places where they can cause failures. In particular, provide fully featured non-production sandbox environments where people can explore and experiment safely, using real data, without affecting real users.

• 从单元测试到全系统集成测试和手动测试，在各个级别上进行彻底的测试[ 3 ]。自动化测试应用广泛，易于理解，对于覆盖正常操作中很少出现的极端情况尤其有价值。

• Test thoroughly at all levels, from unit tests to whole-system integration tests and manual tests [3]. Automated testing is widely used, well understood, and especially valuable for covering corner cases that rarely arise in normal operation.

• 允许快速轻松地从人为错误中恢复，以尽量减少发生故障时的影响。例如，快速回滚配置更改，逐步推出新代码（以便任何意外错误仅影响一小部分用户），并提供重新计算数据的工具（以防旧计算不正确） ）。

• Allow quick and easy recovery from human errors, to minimize the impact in the case of a failure. For example, make it fast to roll back configuration changes, roll out new code gradually (so that any unexpected bugs affect only a small subset of users), and provide tools to recompute data (in case it turns out that the old computation was incorrect).

• 设置详细且清晰的监控，例如性能指标和错误率。在其他工程学科中，这称为遥测。（一旦火箭离开地面，遥测对于跟踪正在发生的情况和了解故障至关重要[ 14 ]。）监控可以向我们显示早期预警信号，并允许我们检查是否违反了任何假设或约束。当问题发生时，指标对于诊断问题非常有价值。

• Set up detailed and clear monitoring, such as performance metrics and error rates. In other engineering disciplines this is referred to as telemetry. (Once a rocket has left the ground, telemetry is essential for tracking what is happening, and for understanding failures [14].) Monitoring can show us early warning signals and allow us to check whether any assumptions or constraints are being violated. When a problem occurs, metrics can be invaluable in diagnosing the issue.

• 实施良好的管理实践和培训——一个复杂而重要的方面，超出了本书的范围。

• Implement good management practices and training—a complex and important aspect, and beyond the scope of this book.

可靠性有多重要？

How Important Is Reliability?

可靠性不仅适用于核电站和空中交通管制软件，更常见的应用也有望可靠运行。业务应用程序中的错误会导致生产力下降（如果报告的数据不正确，还会带来法律风险），而电子商务网站的中断可能会造成巨大的收入损失和声誉损害。

Reliability is not just for nuclear power stations and air traffic control software—more mundane applications are also expected to work reliably. Bugs in business applications cause lost productivity (and legal risks if figures are reported incorrectly), and outages of ecommerce sites can have huge costs in terms of lost revenue and damage to reputation.

即使在“非关键”应用程序中，我们也对用户负责。考虑一位家长将孩子的所有照片和视频存储在您的照片应用程序中 [ 15 ]。如果数据库突然损坏，他们会有什么感觉？他们知道如何从备份中恢复它吗？

Even in “noncritical” applications we have a responsibility to our users. Consider a parent who stores all their pictures and videos of their children in your photo application [15]. How would they feel if that database was suddenly corrupted? Would they know how to restore it from a backup?

在某些情况下，我们可能会选择牺牲可靠性来降低开发成本（例如，为未经证实的市场开发原型产品时）或运营成本（例如，对于利润率非常窄的服务），但我们应该当我们走捷径时要非常小心。

There are situations in which we may choose to sacrifice reliability in order to reduce development cost (e.g., when developing a prototype product for an unproven market) or operational cost (e.g., for a service with a very narrow profit margin)—but we should be very conscious of when we are cutting corners.

描述负载

Describing Load

首先，我们需要简洁地描述系统当前的负载；只有这样我们才能讨论增长问题（如果我们的负载翻倍会发生什么？）。负载可以用一些数字来描述，我们称之为负载参数。参数的最佳选择取决于系统的架构：可能是 Web 服务器每秒的请求数、数据库中的读写比率、聊天室中同时活跃用户的数量、聊天室中的点击率。缓存，或者其他东西。也许平均情况对您来说很重要，或者您的瓶颈可能是由少数极端情况决定的。

First, we need to succinctly describe the current load on the system; only then can we discuss growth questions (what happens if our load doubles?). Load can be described with a few numbers which we call load parameters. The best choice of parameters depends on the architecture of your system: it may be requests per second to a web server, the ratio of reads to writes in a database, the number of simultaneously active users in a chat room, the hit rate on a cache, or something else. Perhaps the average case is what matters for you, or perhaps your bottleneck is dominated by a small number of extreme cases.

为了使这个想法更加具体，我们以 Twitter 为例，使用 2012 年 11 月发布的数据[ 16 ]。Twitter 的两项主要业务是：

To make this idea more concrete, let’s consider Twitter as an example, using data published in November 2012 [16]. Two of Twitter’s main operations are:

发布推文

Post tweet

用户可以向其关注者发布新消息（平均 4.6k 请求/秒，峰值超过 12k 请求/秒）。

A user can publish a new message to their followers (4.6k requests/sec on average, over 12k requests/sec at peak).

主页时间表

Home timeline

用户可以查看他们关注的人发布的推文（300k 请求/秒）。

A user can view tweets posted by the people they follow (300k requests/sec).

只需处理每秒 12,000 次写入（发布推文的峰值速率）就相当容易了。然而，Twitter 的扩展挑战主要不是由于推文数量，而是由于 扇出ⁱⁱ — 每个用户关注很多人，每个用户又被很多人关注。实现这两个操作大致有两种方法：

Simply handling 12,000 writes per second (the peak rate for posting tweets) would be fairly easy. However, Twitter’s scaling challenge is not primarily due to tweet volume, but due to fan-outⁱⁱ—each user follows many people, and each user is followed by many people. There are broadly two ways of implementing these two operations:

1. 发布推文只需将新推文插入到全局推文集合中。当用户请求他们的主页时间线时，查找他们关注的所有人员，找到每个用户的所有推文，然后合并它们（按时间排序）。在如图 1-2所示的关系数据库中 ，您可以编写如下查询：

   SELECT tweets.*, users.* FROM tweets
     JOIN users   ON tweets.sender_id    = users.id
     JOIN follows ON follows.followee_id = users.id
     WHERE follows.follower_id = current_user

2. Posting a tweet simply inserts the new tweet into a global collection of tweets. When a user requests their home timeline, look up all the people they follow, find all the tweets for each of those users, and merge them (sorted by time). In a relational database like in Figure 1-2, you could write a query such as:

   SELECT tweets.*, users.* FROM tweets
     JOIN users   ON tweets.sender_id    = users.id
     JOIN follows ON follows.followee_id = users.id
     WHERE follows.follower_id = current_user

3. 为每个用户的主页时间线维护一个缓存，就像每个接收用户的推文邮箱一样（参见图 1-3）。当用户发布推文时，查找关注该用户的所有人员，并将新推文插入到他们的每个家庭时间线缓存中。这样，读取主时间线的请求就很便宜，因为其结果已提前计算出来。

4. Maintain a cache for each user’s home timeline—like a mailbox of tweets for each recipient user (see Figure 1-3). When a user posts a tweet, look up all the people who follow that user, and insert the new tweet into each of their home timeline caches. The request to read the home timeline is then cheap, because its result has been computed ahead of time.

图 1-2。用于实现 Twitter 主页时间线的简单关系模式。

图 1-3。Twitter 用于向关注者发送推文的数据管道，负载参数截至 2012 年 11 月 [ 16 ]。

Twitter 的第一个版本使用方法 1，但系统难以跟上主页时间线查询的负载，因此该公司改用方法 2。这种方法效果更好，因为发布推文的平均速率几乎比主时间线读取的速率，因此在这种情况下，最好在写入时做更多的工作，而在读取时做更少的工作。

The first version of Twitter used approach 1, but the systems struggled to keep up with the load of home timeline queries, so the company switched to approach 2. This works better because the average rate of published tweets is almost two orders of magnitude lower than the rate of home timeline reads, and so in this case it’s preferable to do more work at write time and less at read time.

然而，方法 2 的缺点是现在发布推文需要大量额外的工作。平均而言，一条推文会发送给大约 75 个关注者，因此每秒 4.6k 条推文会变成每秒 345k 次写入主时间线缓存。但这个平均值掩盖了这样一个事实：每个用户的关注者数量差异很大，有些用户的关注者数量超过 3000 万。这意味着一条推文可能会导致超过 3000 万次写入家庭时间线！及时做到这一点（Twitter 试图在五秒内向关注者发送推文）是一项重大挑战。

However, the downside of approach 2 is that posting a tweet now requires a lot of extra work. On average, a tweet is delivered to about 75 followers, so 4.6k tweets per second become 345k writes per second to the home timeline caches. But this average hides the fact that the number of followers per user varies wildly, and some users have over 30 million followers. This means that a single tweet may result in over 30 million writes to home timelines! Doing this in a timely manner—Twitter tries to deliver tweets to followers within five seconds—is a significant challenge.

在 Twitter 的示例中，每个用户的关注者分布（可能根据这些用户发推文的频率进行加权）是讨论可扩展性的关键负载参数，因为它决定了扇出负载。您的应用程序可能具有非常不同的特征，但您可以应用类似的原则来推理其负载。

In the example of Twitter, the distribution of followers per user (maybe weighted by how often those users tweet) is a key load parameter for discussing scalability, since it determines the fan-out load. Your application may have very different characteristics, but you can apply similar principles to reasoning about its load.

Twitter 轶事的最后一个转折点是：现在方法 2 已经得到了强有力的实施，Twitter 正在转向两种方法的混合。大多数用户的推文在发布时会继续扇出到主页时间线，但少数拥有大量关注者（即名人）的用户会被排除在这种扇出之外。用户可能关注的任何名人的推文都会单独获取，并在读取时与该用户的主页时间线合并，就像方法 1 中一样。这种混合方法能够提供始终如一的良好性能。在介绍了一些更多的技术基础之后，我们将在第 12 章中重新讨论这个例子。

The final twist of the Twitter anecdote: now that approach 2 is robustly implemented, Twitter is moving to a hybrid of both approaches. Most users’ tweets continue to be fanned out to home timelines at the time when they are posted, but a small number of users with a very large number of followers (i.e., celebrities) are excepted from this fan-out. Tweets from any celebrities that a user may follow are fetched separately and merged with that user’s home timeline when it is read, like in approach 1. This hybrid approach is able to deliver consistently good performance. We will revisit this example in Chapter 12 after we have covered some more technical ground.

描述性能

Describing Performance

一旦描述了系统上的负载，您就可以调查负载增加时会发生什么情况。你可以从两个方面来看待它：

Once you have described the load on your system, you can investigate what happens when the load increases. You can look at it in two ways:

• 当您增加负载参数并保持系统资源（CPU、内存、网络带宽等）不变时，系统的性能会受到怎样的影响？

• When you increase a load parameter and keep the system resources (CPU, memory, network bandwidth, etc.) unchanged, how is the performance of your system affected?

• 当增加一个负载参数时，如果要保持性能不变，需要增加多少资源？

• When you increase a load parameter, how much do you need to increase the resources if you want to keep performance unchanged?

这两个问题都需要性能数据，所以让我们简要地看一下系统性能的描述。

Both questions require performance numbers, so let’s look briefly at describing the performance of a system.

在 Hadoop 这样的批处理系统中，我们通常关心吞吐量——每秒可以处理的记录数，或者在一定大小的数据集上运行作业所需的总时间。ⁱⁱⁱ在在线系统中，通常更重要的是服务的 响应时间，即客户端发送请求和接收响应之间的时间。

In a batch processing system such as Hadoop, we usually care about throughput—the number of records we can process per second, or the total time it takes to run a job on a dataset of a certain size.ⁱⁱⁱ In online systems, what’s usually more important is the service’s response time—that is, the time between a client sending a request and receiving a response.

即使您只是一遍又一遍地发出相同的请求，每次尝试都会得到略有不同的响应时间。实际上，在处理各种请求的系统中，响应时间可能会有很大差异。因此，我们需要将响应时间视为 可测量的值的分布，而不是单个数字。

Even if you only make the same request over and over again, you’ll get a slightly different response time on every try. In practice, in a system handling a variety of requests, the response time can vary a lot. We therefore need to think of response time not as a single number, but as a distribution of values that you can measure.

在图 1-4中，每个灰色条代表对服务的请求，其高度显示该请求花费的时间。大多数请求都相当快，但偶尔也会有异常情况需要更长的时间。也许缓慢的请求本质上更昂贵，例如，因为它们处理更多的数据。但即使在您认为所有请求应该花费相同时间的情况下，您也会遇到变化：上下文切换到后台进程、网络数据包丢失和 TCP 重传、垃圾收集可能会引入随机的额外延迟暂停、强制从磁盘读取的页错误、服务器机架中的机械振动 [ 18 ] 或许多其他原因。

In Figure 1-4, each gray bar represents a request to a service, and its height shows how long that request took. Most requests are reasonably fast, but there are occasional outliers that take much longer. Perhaps the slow requests are intrinsically more expensive, e.g., because they process more data. But even in a scenario where you’d think all requests should take the same time, you get variation: random additional latency could be introduced by a context switch to a background process, the loss of a network packet and TCP retransmission, a garbage collection pause, a page fault forcing a read from disk, mechanical vibrations in the server rack [18], or many other causes.

图 1-4。说明平均值和百分位数：对服务的 100 个请求样本的响应时间。

报告服务的平均响应时间 是很常见的。（严格来说，术语“平均”并不指任何特定的公式，但在实践中，它通常被理解为算术平均值 ：给定n 个值，将所有值相加，然后除以n。）但是，平均值如果您想知道“典型”响应时间，这不是一个很好的指标，因为它并不能告诉您有多少用户实际经历了这种延迟。

It’s common to see the average response time of a service reported. (Strictly speaking, the term “average” doesn’t refer to any particular formula, but in practice it is usually understood as the arithmetic mean: given n values, add up all the values, and divide by n.) However, the mean is not a very good metric if you want to know your “typical” response time, because it doesn’t tell you how many users actually experienced that delay.

通常最好使用百分位数。如果您获取响应时间列表并将其从最快到最慢排序，那么中位数就是中间点：例如，如果您的中位数响应时间是 200 毫秒，这意味着一半的请求在不到 200 毫秒的时间内返回，一半的请求在 200 毫秒内返回。您的请求需要比这更长的时间。

Usually it is better to use percentiles. If you take your list of response times and sort it from fastest to slowest, then the median is the halfway point: for example, if your median response time is 200 ms, that means half your requests return in less than 200 ms, and half your requests take longer than that.

如果您想知道用户通常需要等待多长时间，这使得中位数成为一个很好的指标：一半的用户请求在不到中位数响应时间的时间内得到满足，而另一半则需要比中位数更长的时间。中位数也称为第 50 个百分位数，有时缩写为p50。注意，中位数指的是单个请求；如果用户发出多个请求（在一个会话过程中，或者因为单个页面中包含多个资源），则至少其中一个请求比中值慢的概率远大于 50%。

This makes the median a good metric if you want to know how long users typically have to wait: half of user requests are served in less than the median response time, and the other half take longer than the median. The median is also known as the 50th percentile, and sometimes abbreviated as p50. Note that the median refers to a single request; if the user makes several requests (over the course of a session, or because several resources are included in a single page), the probability that at least one of them is slower than the median is much greater than 50%.

为了弄清楚异常值有多严重，您可以查看较高的百分位数：第95、99 和99.9个百分位数很常见（缩写为p95、p99和p999）。它们是响应时间阈值，在该阈值下，95%、99% 或 99.9% 的请求比该特定阈值快。例如，如果第 95 个百分位响应时间为 1.5 秒，则意味着 100 个请求中有 95 个花费的时间少于 1.5 秒，而 100 个请求中有 5 个花费的时间为 1.5 秒或更长。如图 1-4所示。

In order to figure out how bad your outliers are, you can look at higher percentiles: the 95th, 99th, and 99.9th percentiles are common (abbreviated p95, p99, and p999). They are the response time thresholds at which 95%, 99%, or 99.9% of requests are faster than that particular threshold. For example, if the 95th percentile response time is 1.5 seconds, that means 95 out of 100 requests take less than 1.5 seconds, and 5 out of 100 requests take 1.5 seconds or more. This is illustrated in Figure 1-4.

高百分比的响应时间（也称为尾部延迟）非常重要，因为它们直接影响用户的服务体验。例如，亚马逊用 99.9% 的百分位来描述内部服务的响应时间要求，尽管它只影响千分之一的请求。这是因为请求最慢的客户通常是那些帐户上拥有最多数据的客户，因为他们进行了多次购买，也就是说，他们是最有价值的客户 [19 ]。通过确保网站对他们来说速度快来让这些客户满意非常重要：亚马逊还观察到，响应时间增加 100 毫秒会使销售额减少 1% [ 20]，其他人报告说，1 秒的减速会使客户满意度指标降低 16% [ 21 , 22 ]。

High percentiles of response times, also known as tail latencies, are important because they directly affect users’ experience of the service. For example, Amazon describes response time requirements for internal services in terms of the 99.9th percentile, even though it only affects 1 in 1,000 requests. This is because the customers with the slowest requests are often those who have the most data on their accounts because they have made many purchases—that is, they’re the most valuable customers [19]. It’s important to keep those customers happy by ensuring the website is fast for them: Amazon has also observed that a 100 ms increase in response time reduces sales by 1% [20], and others report that a 1-second slowdown reduces a customer satisfaction metric by 16% [21, 22].

另一方面，优化第 99.99 个百分位数（万分之一的请求中最慢的一个）被认为过于昂贵，并且无法为亚马逊的目的带来足够的好处。减少非常高的百分位数的响应时间很困难，因为它们很容易受到您无法控制的随机事件的影响，并且带来的好处正在减少。

On the other hand, optimizing the 99.99th percentile (the slowest 1 in 10,000 requests) was deemed too expensive and to not yield enough benefit for Amazon’s purposes. Reducing response times at very high percentiles is difficult because they are easily affected by random events outside of your control, and the benefits are diminishing.

例如，百分位数通常用于服务级别目标(SLO) 和服务级别协议(SLA)、定义服务的预期性能和可用性的合同。SLA 可能规定，如果服务的中值响应时间小于 200 毫秒且第 99 个百分位数低于 1 秒（如果响应时间更长，则服务可能会关闭），则该服务被视为已启动，并且该服务可能需要至少 99.9% 的时间处于运行状态。这些指标设定了服务客户的期望，并允许客户在未满足 SLA 的情况下要求退款。

For example, percentiles are often used in service level objectives (SLOs) and service level agreements (SLAs), contracts that define the expected performance and availability of a service. An SLA may state that the service is considered to be up if it has a median response time of less than 200 ms and a 99th percentile under 1 s (if the response time is longer, it might as well be down), and the service may be required to be up at least 99.9% of the time. These metrics set expectations for clients of the service and allow customers to demand a refund if the SLA is not met.

排队延迟通常占高百分位响应时间的很大一部分。由于服务器只能并行处理少量事物（例如，受 CPU 核心数量的限制），因此只需要少量缓慢的请求即可阻止后续请求的处理，这种效果有时称为队头阻塞。即使服务器上处理这些后续请求的速度很快，客户端也会因为等待先前请求完成的时间而看到整体响应时间很慢。由于这种影响，测量客户端的响应时间非常重要。

Queueing delays often account for a large part of the response time at high percentiles. As a server can only process a small number of things in parallel (limited, for example, by its number of CPU cores), it only takes a small number of slow requests to hold up the processing of subsequent requests—an effect sometimes known as head-of-line blocking. Even if those subsequent requests are fast to process on the server, the client will see a slow overall response time due to the time waiting for the prior request to complete. Due to this effect, it is important to measure response times on the client side.

当为了测试系统的可扩展性而人为生成负载时，负载生成客户端需要独立于响应时间持续发送请求。如果客户端在发送下一个请求之前等待上一个请求完成，则该行为会人为地使测试中的队列比实际情况短，从而使测量结果出现偏差 [23 ]。

When generating load artificially in order to test the scalability of a system, the load-generating client needs to keep sending requests independently of the response time. If the client waits for the previous request to complete before sending the next one, that behavior has the effect of artificially keeping the queues shorter in the test than they would be in reality, which skews the measurements [23].

图 1-5。当需要多个后端调用来服务一个请求时，只需一个缓慢的后端请求即可减慢整个最终用户请求的速度。

应对负荷的方法

Approaches for Coping with Load

现在我们已经讨论了描述负载的参数和衡量性能的指标，我们可以开始认真讨论可扩展性：即使负载参数增加了一定量，我们如何保持良好的性能？

Now that we have discussed the parameters for describing load and metrics for measuring performance, we can start discussing scalability in earnest: how do we maintain good performance even when our load parameters increase by some amount?

适合某一级别负载的架构不太可能应对 10 倍的负载。如果您正在开发快速增长的服务，那么您可能需要在负载每次增加一个数量级时重新考虑您的架构，甚至可能比这更频繁。

An architecture that is appropriate for one level of load is unlikely to cope with 10 times that load. If you are working on a fast-growing service, it is therefore likely that you will need to rethink your architecture on every order of magnitude load increase—or perhaps even more often than that.

人们经常谈论纵向扩展（垂直扩展，迁移到更强大的机器）和横向扩展（水平扩展，将负载分布在多个较小的机器上）之间的二分法。在多台机器之间分配负载也称为无共享 架构。可以在单台机器上运行的系统通常更简单，但高端机器可能会变得非常昂贵，因此非常密集的工作负载通常无法避免横向扩展。实际上，好的架构通常涉及多种方法的实用组合：例如，使用几台功能相当强大的机器仍然比使用大量小型虚拟机更简单、更便宜。

People often talk of a dichotomy between scaling up (vertical scaling, moving to a more powerful machine) and scaling out (horizontal scaling, distributing the load across multiple smaller machines). Distributing load across multiple machines is also known as a shared-nothing architecture. A system that can run on a single machine is often simpler, but high-end machines can become very expensive, so very intensive workloads often can’t avoid scaling out. In reality, good architectures usually involve a pragmatic mixture of approaches: for example, using several fairly powerful machines can still be simpler and cheaper than a large number of small virtual machines.

有些系统是弹性的，这意味着它们可以在检测到负载增加时自动添加计算资源，而其他系统则手动扩展（人类分析容量并决定向系统添加更多机器）。如果负载高度不可预测，弹性系统可能会很有用，但手动扩展的系统更简单，并且操作意外可能更少（请参阅“重新平衡分区”）。

Some systems are elastic, meaning that they can automatically add computing resources when they detect a load increase, whereas other systems are scaled manually (a human analyzes the capacity and decides to add more machines to the system). An elastic system can be useful if load is highly unpredictable, but manually scaled systems are simpler and may have fewer operational surprises (see “Rebalancing Partitions”).

虽然在多台机器上分发无状态服务相当简单，但将有状态数据系统从单个节点转移到分布式设置可能会带来很多额外的复杂性。因此，直到最近，普遍的看法是将数据库保留在单个节点上（纵向扩展），直到扩展成本或高可用性要求迫使您将其分布式。

While distributing stateless services across multiple machines is fairly straightforward, taking stateful data systems from a single node to a distributed setup can introduce a lot of additional complexity. For this reason, common wisdom until recently was to keep your database on a single node (scale up) until scaling cost or high-availability requirements forced you to make it distributed.

随着分布式系统的工具和抽象变得更好，这种常识可能会改变，至少对于某些类型的应用程序来说是这样。可以想象，分布式数据系统将成为未来的默认系统，即使对于不处理大量数据或流量的用例也是如此。在本书的其余部分中，我们将讨论多种分布式数据系统，并讨论它们不仅在可扩展性方面的表现，而且在易用性和可维护性方面的表现。

As the tools and abstractions for distributed systems get better, this common wisdom may change, at least for some kinds of applications. It is conceivable that distributed data systems will become the default in the future, even for use cases that don’t handle large volumes of data or traffic. Over the course of the rest of this book we will cover many kinds of distributed data systems, and discuss how they fare not just in terms of scalability, but also ease of use and maintainability.

大规模运行的系统架构通常对于应用程序来说是高度特定的——不存在通用的、一刀切的可扩展架构（非正式地称为“魔法缩放酱” ）。问题可能是读取量、写入量、要存储的数据量、数据的复杂性、响应时间要求、访问模式，或者（通常）所有这些加上更多问题的某种混合。

The architecture of systems that operate at large scale is usually highly specific to the application—there is no such thing as a generic, one-size-fits-all scalable architecture (informally known as magic scaling sauce). The problem may be the volume of reads, the volume of writes, the volume of data to store, the complexity of the data, the response time requirements, the access patterns, or (usually) some mixture of all of these plus many more issues.

例如，设计为每秒处理 100,000 个请求（每个请求大小为 1 kB）的系统与设计为每分钟处理 3 个请求（每个请求大小为 2 GB）的系统看起来非常不同，尽管这两个系统具有相同的性能数据吞吐量。

For example, a system that is designed to handle 100,000 requests per second, each 1 kB in size, looks very different from a system that is designed for 3 requests per minute, each 2 GB in size—even though the two systems have the same data throughput.

对于特定应用程序来说，可以很好地扩展的架构是围绕哪些操作是常见的、哪些是罕见的（负载参数）的假设而构建的。如果这些假设被证明是错误的，那么扩展的工程工作往好了说就是浪费，往坏了说是适得其反。在早期启动或未经验证的产品中，能够快速迭代产品功能通常比扩展到某些假设的未来负载更重要。

An architecture that scales well for a particular application is built around assumptions of which operations will be common and which will be rare—the load parameters. If those assumptions turn out to be wrong, the engineering effort for scaling is at best wasted, and at worst counterproductive. In an early-stage startup or an unproven product it’s usually more important to be able to iterate quickly on product features than it is to scale to some hypothetical future load.

尽管它们特定于特定应用程序，但可扩展架构通常是由通用构建块构建的，并以熟悉的模式排列。在本书中，我们讨论这些构建块和模式。

Even though they are specific to a particular application, scalable architectures are nevertheless usually built from general-purpose building blocks, arranged in familiar patterns. In this book we discuss those building blocks and patterns.

可操作性：让操作变得简单

Operability: Making Life Easy for Operations

有人提出，“良好的操作通常可以解决不良（或不完整）软件的局限性，但良好的软件无法在不良操作的情况下可靠运行”[ 12 ]。虽然操作的某些方面可以而且应该自动化，但仍然需要人类首先设置自动化并确保其正常工作。

It has been suggested that “good operations can often work around the limitations of bad (or incomplete) software, but good software cannot run reliably with bad operations” [12]. While some aspects of operations can and should be automated, it is still up to humans to set up that automation in the first place and to make sure it’s working correctly.

运营团队对于保持软件系统平稳运行至关重要。一个好的运营团队通常负责以下以及更多的事情 [ 29 ]：

Operations teams are vital to keeping a software system running smoothly. A good operations team typically is responsible for the following, and more [29]:

• 监控系统的健康状况并在出现不良状态时快速恢复服务

• Monitoring the health of the system and quickly restoring service if it goes into a bad state

• 追踪问题的原因，例如系统故障或性能下降

• Tracking down the cause of problems, such as system failures or degraded performance

• 保持软件和平台最新，包括安全补丁

• Keeping software and platforms up to date, including security patches

• 密切关注不同系统如何相互影响，以便在造成损害之前避免有问题的更改

• Keeping tabs on how different systems affect each other, so that a problematic change can be avoided before it causes damage

• 预测未来的问题并在问题发生之前解决它们（例如，容量规划）

• Anticipating future problems and solving them before they occur (e.g., capacity planning)

• 建立部署、配置管理等方面的良好实践和工具

• Establishing good practices and tools for deployment, configuration management, and more

• 执行复杂的维护任务，例如将应用程序从一个平台移动到另一个平台

• Performing complex maintenance tasks, such as moving an application from one platform to another

• 在进行配置更改时维护系统的安全

• Maintaining the security of the system as configuration changes are made

• 定义使运营可预测并有助于保持生产环境稳定的流程

• Defining processes that make operations predictable and help keep the production environment stable

• 即使个人来来去去，也能保留组织对系统的了解

• Preserving the organization’s knowledge about the system, even as individual people come and go

良好的可操作性意味着让日常任务变得简单，让运营团队能够将精力集中在高价值的活动上。数据系统可以做很多事情来简化日常任务，包括：

Good operability means making routine tasks easy, allowing the operations team to focus their efforts on high-value activities. Data systems can do various things to make routine tasks easy, including:

• 通过良好的监控，提供对系统运行时行为和内部结构的可见性

• Providing visibility into the runtime behavior and internals of the system, with good monitoring

• 为自动化和与标准工具的集成提供良好的支持

• Providing good support for automation and integration with standard tools

• 避免对单个机器的依赖（允许关闭机器进行维护，而整个系统继续不间断运行）

• Avoiding dependency on individual machines (allowing machines to be taken down for maintenance while the system as a whole continues running uninterrupted)

• 提供良好的文档和易于理解的操作模型（“如果我做 X，Y 就会发生”）

• Providing good documentation and an easy-to-understand operational model (“If I do X, Y will happen”)

• 提供良好的默认行为，同时也让管理员可以在需要时自由地覆盖默认值

• Providing good default behavior, but also giving administrators the freedom to override defaults when needed

• 在适当的情况下进行自我修复，但还可以在需要时让管理员手动控制系统状态

• Self-healing where appropriate, but also giving administrators manual control over the system state when needed

• 表现出可预测的行为，最大限度地减少意外

• Exhibiting predictable behavior, minimizing surprises

简单性：管理复杂性

Simplicity: Managing Complexity

小型软件项目可以拥有非常简单且富有表现力的代码，但随着项目变得更大，它们通常会变得非常复杂且难以理解。这种复杂性降低了每个需要在系统上工作的人的速度，进一步增加了维护成本。陷入复杂性的软件项目有时被描述为一个大泥球 [ 30 ]。

Small software projects can have delightfully simple and expressive code, but as projects get larger, they often become very complex and difficult to understand. This complexity slows down everyone who needs to work on the system, further increasing the cost of maintenance. A software project mired in complexity is sometimes described as a big ball of mud [30].

复杂性有各种可能的症状：状态空间的爆炸、模块的紧密耦合、纠结的依赖关系、不一致的命名和术语、旨在解决性能问题的黑客、解决其他地方问题的特殊情况等等。关于这个话题 已经说了很多了[ 31,32,33 ]。

There are various possible symptoms of complexity: explosion of the state space, tight coupling of modules, tangled dependencies, inconsistent naming and terminology, hacks aimed at solving performance problems, special-casing to work around issues elsewhere, and many more. Much has been said on this topic already [31, 32, 33].

当复杂性导致维护变得困难时，预算和时间表常常会超支。在复杂的软件中，进行更改时引入错误的风险也更大：当开发人员更难理解和推理系统时，隐藏的假设、意想不到的后果和意外的交互更容易被忽视。相反，降低复杂性可以大大提高软件的可维护性，因此简单性应该是我们构建的系统的一个关键目标。

When complexity makes maintenance hard, budgets and schedules are often overrun. In complex software, there is also a greater risk of introducing bugs when making a change: when the system is harder for developers to understand and reason about, hidden assumptions, unintended consequences, and unexpected interactions are more easily overlooked. Conversely, reducing complexity greatly improves the maintainability of software, and thus simplicity should be a key goal for the systems we build.

使系统更简单并不一定意味着减少其功能；它也可能意味着消除偶然的复杂性。Moseley 和 Marks [ 32 ] 将复杂性定义为偶然的，如果它不是软件解决的问题所固有的（如用户所见），而是仅在实现中出现。

Making a system simpler does not necessarily mean reducing its functionality; it can also mean removing accidental complexity. Moseley and Marks [32] define complexity as accidental if it is not inherent in the problem that the software solves (as seen by the users) but arises only from the implementation.

抽象 是我们消除偶然复杂性的最佳工具之一。良好的抽象可以在干净、易于理解的外观背后隐藏大量的实现细节。良好的抽象还可以用于广泛的不同应用。这种重用不仅比多次重新实现类似的东西更有效，而且还可以带来更高质量的软件，因为抽象组件的质量改进有利于所有使用它的应用程序。

One of the best tools we have for removing accidental complexity is abstraction. A good abstraction can hide a great deal of implementation detail behind a clean, simple-to-understand façade. A good abstraction can also be used for a wide range of different applications. Not only is this reuse more efficient than reimplementing a similar thing multiple times, but it also leads to higher-quality software, as quality improvements in the abstracted component benefit all applications that use it.

例如，高级编程语言是隐藏机器代码、CPU 寄存器和系统调用的抽象。SQL 是一种抽象，它隐藏了复杂的磁盘和内存数据结构、来自其他客户端的并发请求以及崩溃后的不一致。当然，在用高级语言编程时，我们仍然使用机器代码；我们只是不 直接使用它，因为编程语言的抽象使我们不必考虑它。

For example, high-level programming languages are abstractions that hide machine code, CPU registers, and syscalls. SQL is an abstraction that hides complex on-disk and in-memory data structures, concurrent requests from other clients, and inconsistencies after crashes. Of course, when programming in a high-level language, we are still using machine code; we are just not using it directly, because the programming language abstraction saves us from having to think about it.

然而，找到好的抽象是非常困难的。在分布式系统领域，虽然有很多好的算法，但我们应该如何将它们包装成抽象来帮助我们将系统的复杂性保持在可管理的水平，这一点还不清楚。

However, finding good abstractions is very hard. In the field of distributed systems, although there are many good algorithms, it is much less clear how we should be packaging them into abstractions that help us keep the complexity of the system at a manageable level.

在本书中，我们将密切关注良好的抽象，这些抽象使我们能够将大型系统的各个部分提取为定义良好的、可重用的组件。

Throughout this book, we will keep our eyes open for good abstractions that allow us to extract parts of a large system into well-defined, reusable components.

可进化性：让改变变得容易

Evolvability: Making Change Easy

您的系统要求永远保持不变的可能性极小。它们更有可能不断变化：您了解新的事实，出现以前未预料到的用例，业务优先级发生变化，用户请求新功能，新平台取代旧平台，法律或监管要求发生变化，系统的增长迫使架构发生变化， ETC。

It’s extremely unlikely that your system’s requirements will remain unchanged forever. They are much more likely to be in constant flux: you learn new facts, previously unanticipated use cases emerge, business priorities change, users request new features, new platforms replace old platforms, legal or regulatory requirements change, growth of the system forces architectural changes, etc.

在组织流程方面，敏捷工作模式提供了适应变化的框架。敏捷社区还开发了技术工具和模式，这些工具和模式在频繁变化的环境中开发软件时很有帮助，例如测试驱动开发（TDD）和重构。

In terms of organizational processes, Agile working patterns provide a framework for adapting to change. The Agile community has also developed technical tools and patterns that are helpful when developing software in a frequently changing environment, such as test-driven development (TDD) and refactoring.

这些敏捷技术的大多数讨论都集中在相当小的本地规模（同一应用程序中的几个源代码文件）。在本书中，我们寻找在更大的数据系统级别上提高敏捷性的方法，该系统可能由具有不同特征的几个不同的应用程序或服务组成。例如，您将如何“重构”Twitter 的用于组装主页时间线（“描述负载”）的架构，从方法 1 到方法 2？

Most discussions of these Agile techniques focus on a fairly small, local scale (a couple of source code files within the same application). In this book, we search for ways of increasing agility on the level of a larger data system, perhaps consisting of several different applications or services with different characteristics. For example, how would you “refactor” Twitter’s architecture for assembling home timelines (“Describing Load”) from approach 1 to approach 2?

修改数据系统并使其适应不断变化的需求的容易程度与其简单性和抽象性密切相关：简单且易于理解的系统通常比复杂的系统更容易修改。但由于这是一个如此重要的想法，我们将使用不同的词来指代数据系统级别的敏捷性：可进化性 [ 34 ]。

The ease with which you can modify a data system, and adapt it to changing requirements, is closely linked to its simplicity and its abstractions: simple and easy-to-understand systems are usually easier to modify than complex ones. But since this is such an important idea, we will use a different word to refer to agility on a data system level: evolvability [34].

NoSQL 的诞生

The Birth of NoSQL

现在，进入 2010 年代，NoSQL是推翻关系模型统治地位的最新尝试。“NoSQL”这个名字很不幸，因为它实际上并不指任何特定的技术——它最初只是作为 2009 年开源、分布式、非关系数据库聚会的一个吸引人的 Twitter 标签[3 ]。尽管如此，这个词还是引起了人们的注意，并迅速在网络创业社区内外传播开来。许多有趣的数据库系统现在都与 #NoSQL 标签相关联，并且它已被追溯重新解释为Not Only SQL [ 4 ]。

Now, in the 2010s, NoSQL is the latest attempt to overthrow the relational model’s dominance. The name “NoSQL” is unfortunate, since it doesn’t actually refer to any particular technology—it was originally intended simply as a catchy Twitter hashtag for a meetup on open source, distributed, nonrelational databases in 2009 [3]. Nevertheless, the term struck a nerve and quickly spread through the web startup community and beyond. A number of interesting database systems are now associated with the #NoSQL hashtag, and it has been retroactively reinterpreted as Not Only SQL [4].

采用 NoSQL 数据库背后有多种驱动力，包括：

There are several driving forces behind the adoption of NoSQL databases, including:

• 需要比关系数据库可以轻松实现的更高可扩展性，包括非常大的数据集或非常高的写入吞吐量

• A need for greater scalability than relational databases can easily achieve, including very large datasets or very high write throughput

• 与商业数据库产品相比，人们普遍偏爱免费和开源软件

• A widespread preference for free and open source software over commercial database products

• 关系模型不能很好支持的专门查询操作

• Specialized query operations that are not well supported by the relational model

• 对关系模式的限制性感到沮丧，并渴望更动态和更具表现力的数据模型 [ 5 ]

• Frustration with the restrictiveness of relational schemas, and a desire for a more dynamic and expressive data model [5]

不同的应用程序有不同的要求，一个用例的最佳技术选择可能与另一个用例的最佳技术选择不同。因此，在可预见的未来，关系数据库似乎将继续与各种非关系数据存储一起使用——这种想法有时被称为多语言持久性 [ 3 ]。

Different applications have different requirements, and the best choice of technology for one use case may well be different from the best choice for another use case. It therefore seems likely that in the foreseeable future, relational databases will continue to be used alongside a broad variety of nonrelational datastores—an idea that is sometimes called polyglot persistence [3].

对象关系不匹配

The Object-Relational Mismatch

如今，大多数应用程序开发都是用面向对象的编程语言完成的，这导致了对 SQL 数据模型的普遍批评：如果数据存储在关系表中，则应用程序代码中的对象和数据库模型之间需要一个尴尬的转换层表、行和列。模型之间的脱节有时称为 阻抗失配。^我

Most application development today is done in object-oriented programming languages, which leads to a common criticism of the SQL data model: if data is stored in relational tables, an awkward translation layer is required between the objects in the application code and the database model of tables, rows, and columns. The disconnect between the models is sometimes called an impedance mismatch.ⁱ

ActiveRecord 和 Hibernate 等对象关系映射 (ORM) 框架减少了该转换层所需的样板代码量，但它们无法完全隐藏两个模型之间的差异。

Object-relational mapping (ORM) frameworks like ActiveRecord and Hibernate reduce the amount of boilerplate code required for this translation layer, but they can’t completely hide the differences between the two models.

例如，图 2-1说明了如何在关系模式中表达简历（LinkedIn 个人资料）。整个配置文件可以通过唯一标识符 来识别 user_id。first_name诸如和之类的字段last_name每个用户只出现一次，因此可以将它们建模为users表中的列。然而，大多数人在其职业生涯中从事过不止一份工作（职位），并且人们可能有不同数量的教育时期和任意数量的联系信息。用户与这些项目之间存在一对多的关系，可以用多种方式表示：

For example, Figure 2-1 illustrates how a résumé (a LinkedIn profile) could be expressed in a relational schema. The profile as a whole can be identified by a unique identifier, user_id. Fields like first_name and last_name appear exactly once per user, so they can be modeled as columns on the users table. However, most people have had more than one job in their career (positions), and people may have varying numbers of periods of education and any number of pieces of contact information. There is a one-to-many relationship from the user to these items, which can be represented in various ways:

• 在传统的 SQL 模型（SQL:1999 之前）中，最常见的规范化表示是将职位、教育和联系信息放在单独的表中，并使用外键引用该表，如图users2-1所示。

• In the traditional SQL model (prior to SQL:1999), the most common normalized representation is to put positions, education, and contact information in separate tables, with a foreign key reference to the users table, as in Figure 2-1.

• SQL 标准的更高版本添加了对结构化数据类型和 XML 数据的支持；这允许将多值数据存储在单行中，并支持在这些文档内进行查询和索引。Oracle、IBM DB2、MS SQL Server 和 PostgreSQL [ 6 , 7 ]不同程度地支持这些功能。JSON 数据类型还受到多种数据库的支持，包括 IBM DB2、MySQL 和 PostgreSQL [ 8 ]。

• Later versions of the SQL standard added support for structured datatypes and XML data; this allowed multi-valued data to be stored within a single row, with support for querying and indexing inside those documents. These features are supported to varying degrees by Oracle, IBM DB2, MS SQL Server, and PostgreSQL [6, 7]. A JSON datatype is also supported by several databases, including IBM DB2, MySQL, and PostgreSQL [8].

• 第三种选择是将工作、教育和联系信息编码为 JSON 或 XML 文档，将其存储在数据库的文本列中，并让应用程序解释其结构和内容。在此设置中，您通常无法使用数据库来查询该编码列内的值。

• A third option is to encode jobs, education, and contact info as a JSON or XML document, store it on a text column in the database, and let the application interpret its structure and content. In this setup, you typically cannot use the database to query for values inside that encoded column.

图 2-1。使用关系模式表示 LinkedIn 个人资料。比尔·盖茨的照片由维基共享资源、巴西通讯社 Ricardo Stuckert 提供。

对于像简历这样的数据结构（主要是一个独立的文档），JSON 表示可能非常合适：请参见示例 2-1。JSON 的优点是比 XML 简单得多。面向文档的数据库，如 MongoDB [ 9 ]、RethinkDB [ 10 ]、CouchDB [ 11 ] 和 Espresso [ 12 ] 支持这种数据模型。

For a data structure like a résumé, which is mostly a self-contained document, a JSON representation can be quite appropriate: see Example 2-1. JSON has the appeal of being much simpler than XML. Document-oriented databases like MongoDB [9], RethinkDB [10], CouchDB [11], and Espresso [12] support this data model.

{
  "user_id":     251,
  "first_name":  "Bill",
  "last_name":   "Gates",
  "summary":     "Co-chair of the Bill & Melinda Gates... Active blogger.",
  "region_id":   "us:91",
  "industry_id": 131,
  "photo_url":   "/p/7/000/253/05b/308dd6e.jpg",
  "positions": [
    {"job_title": "Co-chair", "organization": "Bill & Melinda Gates Foundation"},
    {"job_title": "Co-founder, Chairman", "organization": "Microsoft"}
  ],
  "education": [
    {"school_name": "Harvard University",       "start": 1973, "end": 1975},
    {"school_name": "Lakeside School, Seattle", "start": null, "end": null}
  ],
  "contact_info": {
    "blog":    "http://thegatesnotes.com",
    "twitter": "http://twitter.com/BillGates"
  }
}

{
  "user_id":     251,
  "first_name":  "Bill",
  "last_name":   "Gates",
  "summary":     "Co-chair of the Bill & Melinda Gates... Active blogger.",
  "region_id":   "us:91",
  "industry_id": 131,
  "photo_url":   "/p/7/000/253/05b/308dd6e.jpg",
  "positions": [
    {"job_title": "Co-chair", "organization": "Bill & Melinda Gates Foundation"},
    {"job_title": "Co-founder, Chairman", "organization": "Microsoft"}
  ],
  "education": [
    {"school_name": "Harvard University",       "start": 1973, "end": 1975},
    {"school_name": "Lakeside School, Seattle", "start": null, "end": null}
  ],
  "contact_info": {
    "blog":    "http://thegatesnotes.com",
    "twitter": "http://twitter.com/BillGates"
  }
}

一些开发人员认为 JSON 模型减少了应用程序代码和存储层之间的阻抗不匹配。然而，正如我们将在第 4 章中看到的，JSON 作为数据编码格式也存在问题。缺乏模式经常被认为是一个优点；我们将在“文档模型中的架构灵活性”中讨论这一点。

Some developers feel that the JSON model reduces the impedance mismatch between the application code and the storage layer. However, as we shall see in Chapter 4, there are also problems with JSON as a data encoding format. The lack of a schema is often cited as an advantage; we will discuss this in “Schema flexibility in the document model”.

JSON 表示比图 2-1中的多表模式 具有更好的局部性。如果要获取关系示例中的配置文件，则需要执行多个查询（通过 查询每个表）或在表及其下级表之间执行混乱的多路联接。在 JSON 表示中，所有相关信息都集中在一处，一次查询就足够了。user_idusers

The JSON representation has better locality than the multi-table schema in Figure 2-1. If you want to fetch a profile in the relational example, you need to either perform multiple queries (query each table by user_id) or perform a messy multi-way join between the users table and its subordinate tables. In the JSON representation, all the relevant information is in one place, and one query is sufficient.

从用户个人资料到用户的职位、教育经历和联系信息的一对多关系隐含着数据中的树形结构，而 JSON 表示使这种树形结构变得明确（见图 2-2 ）。

The one-to-many relationships from the user profile to the user’s positions, educational history, and contact information imply a tree structure in the data, and the JSON representation makes this tree structure explicit (see Figure 2-2).

图 2-2。一对多关系形成树结构。

多对一和多对多关系

Many-to-One and Many-to-Many Relationships

在上一节的示例 2-1中，region_id和industry_id是作为 ID 给出的，而不是作为纯文本字符串"Greater Seattle Area"和"Philanthropy"。为什么？

In Example 2-1 in the preceding section, region_id and industry_id are given as IDs, not as plain-text strings "Greater Seattle Area" and "Philanthropy". Why?

如果用户界面具有用于输入地区和行业的自由文本字段，则将它们存储为纯文本字符串是有意义的。但是，拥有标准化的地理区域和行业列表并让用户从下拉列表或自动完成器中进行选择是有好处的：

If the user interface has free-text fields for entering the region and the industry, it makes sense to store them as plain-text strings. But there are advantages to having standardized lists of geographic regions and industries, and letting users choose from a drop-down list or autocompleter:

• 跨个人资料的风格和拼写一致

• Consistent style and spelling across profiles

• 避免歧义（例如，如果有多个城市同名）

• Avoiding ambiguity (e.g., if there are several cities with the same name)

• 易于更新——名称仅存储在一个位置，因此如果需要更改（例如，由于政治事件而更改城市名称），可以轻松进行全面更新

• Ease of updating—the name is stored in only one place, so it is easy to update across the board if it ever needs to be changed (e.g., change of a city name due to political events)

• 本地化支持——当网站翻译成其他语言时，可以对标准化列表进行本地化，以便以浏览者的语言显示地区和行业

• Localization support—when the site is translated into other languages, the standardized lists can be localized, so the region and industry can be displayed in the viewer’s language

• 更好的搜索 - 例如，搜索华盛顿州的慈善家可以匹配此配置文件，因为区域列表可以编码西雅图位于华盛顿的事实（这从字符串中看不出来"Greater Seattle Area"）

• Better search—e.g., a search for philanthropists in the state of Washington can match this profile, because the list of regions can encode the fact that Seattle is in Washington (which is not apparent from the string "Greater Seattle Area")

无论存储 ID 还是文本字符串都存在重复问题。当您使用 ID 时，对人类有意义的信息（例如Philanthropy一词）仅存储在一个位置，而引用它的所有内容都使用 ID（仅在数据库中有意义）。当您直接存储文本时，您会在使用该文本的每个记录中复制对人类有意义的信息。

Whether you store an ID or a text string is a question of duplication. When you use an ID, the information that is meaningful to humans (such as the word Philanthropy) is stored in only one place, and everything that refers to it uses an ID (which only has meaning within the database). When you store the text directly, you are duplicating the human-meaningful information in every record that uses it.

使用ID的优点在于，因为它对人类没有意义，所以它永远不需要改变：即使它标识的信息发生变化，ID也可以保持不变。任何对人类有意义的事情都可能需要在未来的某个时候进行更改，如果该信息重复，则所有冗余副本都需要更新。这会产生写入开销，并带来不一致的风险（其中某些信息副本已更新，但其他副本未更新）。删除此类重复是数据库规范化背后的关键思想。^二、

The advantage of using an ID is that because it has no meaning to humans, it never needs to change: the ID can remain the same, even if the information it identifies changes. Anything that is meaningful to humans may need to change sometime in the future—and if that information is duplicated, all the redundant copies need to be updated. That incurs write overheads, and risks inconsistencies (where some copies of the information are updated but others aren’t). Removing such duplication is the key idea behind normalization in databases.ⁱⁱ

不幸的是，规范化这些数据需要多对一的关系（许多人生活在一个特定的地区，许多人在一个特定的行业工作），这不能很好地适应文档模型。在关系数据库中，通过 ID 引用其他表中的行是很正常的，因为连接很容易。在文档数据库中，一对多树结构不需要联接，并且对联接的支持通常很弱。^三、

Unfortunately, normalizing this data requires many-to-one relationships (many people live in one particular region, many people work in one particular industry), which don’t fit nicely into the document model. In relational databases, it’s normal to refer to rows in other tables by ID, because joins are easy. In document databases, joins are not needed for one-to-many tree structures, and support for joins is often weak.ⁱⁱⁱ

如果数据库本身不支持联接，则必须通过对数据库进行多个查询来模拟应用程序代码中的联接。（在这种情况下，地区和行业的列表可能很小并且变化很慢，应用程序可以简单地将它们保存在内存中。但是，尽管如此，进行连接的工作还是从数据库转移到了应用程序代码。）

If the database itself does not support joins, you have to emulate a join in application code by making multiple queries to the database. (In this case, the lists of regions and industries are probably small and slow-changing enough that the application can simply keep them in memory. But nevertheless, the work of making the join is shifted from the database to the application code.)

此外，即使应用程序的初始版本非常适合无连接文档模型，随着功能添加到应用程序中，数据也有变得更加互连的趋势。例如，考虑我们可以对简历示例进行一些更改：

Moreover, even if the initial version of an application fits well in a join-free document model, data has a tendency of becoming more interconnected as features are added to applications. For example, consider some changes we could make to the résumé example:

组织和学校作为实体

Organizations and schools as entities

在前面的描述中，organization（用户工作的公司）和school_name （他们就读的公司）只是字符串。也许它们应该是对实体的引用？ 然后每个组织、学校或大学都可以拥有自己的网页（带有徽标、新闻提要等）；每份简历都可以链接到它提到的组织和学校，并包含它们的徽标和其他信息（参见图 2-3，了解 LinkedIn 的示例）。

In the previous description, organization (the company where the user worked) and school_name (where they studied) are just strings. Perhaps they should be references to entities instead? Then each organization, school, or university could have its own web page (with logo, news feed, etc.); each résumé could link to the organizations and schools that it mentions, and include their logos and other information (see Figure 2-3 for an example from LinkedIn).

建议

Recommendations

假设您要添加一项新功能：一个用户可以为另一个用户编写推荐。推荐会显示在被推荐用户的简历上，以及提出推荐的用户的姓名和照片。如果推荐者更新了他们的照片，他们写的任何推荐都需要反映新照片。因此，推荐应该参考作者的简介。

Say you want to add a new feature: one user can write a recommendation for another user. The recommendation is shown on the résumé of the user who was recommended, together with the name and photo of the user making the recommendation. If the recommender updates their photo, any recommendations they have written need to reflect the new photo. Therefore, the recommendation should have a reference to the author’s profile.

图 2-3。公司名称不仅仅是一个字符串，而是指向公司实体的链接。linkedin.com 的屏幕截图。

图 2-4说明了这些新功能如何需要多对多关系。每个虚线矩形内的数据可以分组为一个文档，但对组织、学校和其他用户的引用需要表示为引用，并且在查询时需要联接。

Figure 2-4 illustrates how these new features require many-to-many relationships. The data within each dotted rectangle can be grouped into one document, but the references to organizations, schools, and other users need to be represented as references, and require joins when queried.

图 2-4。通过多对多关系扩展简历。

文档数据库正在重复历史吗？

Are Document Databases Repeating History?

虽然多对多关系和联接在关系数据库中经常使用，但文档数据库和 NoSQL 重新引发了关于如何最好地在数据库中表示此类关系的争论。这场争论比 NoSQL 更古老——事实上，它可以追溯到最早的计算机化数据库系统。

While many-to-many relationships and joins are routinely used in relational databases, document databases and NoSQL reopened the debate on how best to represent such relationships in a database. This debate is much older than NoSQL—in fact, it goes back to the very earliest computerized database systems.

20 世纪 70 年代最流行的商业数据处理数据库是 IBM 的信息管理系统(IMS)，最初是为阿波罗太空计划中的库存管理而开发的，并于 1968 年首次商业发布[ 13 ]。它至今仍在使用和维护，在 IBM 大型机上的 OS/390 上运行 [ 14 ]。

The most popular database for business data processing in the 1970s was IBM’s Information Management System (IMS), originally developed for stock-keeping in the Apollo space program and first commercially released in 1968 [13]. It is still in use and maintained today, running on OS/390 on IBM mainframes [14].

IMS 的设计使用了一种相当简单的数据模型，称为层次模型，它与文档数据库使用的 JSON 模型有一些显着的相似之处 [ 2 ]。它将所有数据表示为嵌套在记录中的记录树，非常类似于图 2-2的 JSON 结构。

The design of IMS used a fairly simple data model called the hierarchical model, which has some remarkable similarities to the JSON model used by document databases [2]. It represented all data as a tree of records nested within records, much like the JSON structure of Figure 2-2.

与文档数据库一样，IMS 非常适合一对多关系，但它使多对多关系变得困难，并且不支持联接。开发人员必须决定是复制（非规范化）数据还是手动解析从一条记录到另一条记录的引用。20 世纪 60 年代和 70 年代的这些问题非常类似于开发人员今天在文档数据库中遇到的问题 [ 15 ]。

Like document databases, IMS worked well for one-to-many relationships, but it made many-to-many relationships difficult, and it didn’t support joins. Developers had to decide whether to duplicate (denormalize) data or to manually resolve references from one record to another. These problems of the 1960s and ’70s were very much like the problems that developers are running into with document databases today [15].

为了解决分层模型的局限性，人们提出了各种解决方案。其中最突出的两个模型是关系模型（后来成为 SQL，并占领了世界）和网络模型（最初拥有大量追随者，但最终逐渐变得默默无闻）。这两个阵营之间的“大辩论”持续了 20 世纪 70 年代的大部分时间[ 2 ]。

Various solutions were proposed to solve the limitations of the hierarchical model. The two most prominent were the relational model (which became SQL, and took over the world) and the network model (which initially had a large following but eventually faded into obscurity). The “great debate” between these two camps lasted for much of the 1970s [2].

由于这两个模型所解决的问题在今天仍然具有重要意义，因此有必要根据今天的情况简要回顾一下这场争论。

Since the problem that the two models were solving is still so relevant today, it’s worth briefly revisiting this debate in today’s light.

当今的关系数据库与文档数据库

Relational Versus Document Databases Today

在将关系数据库与文档数据库进行比较时，需要考虑许多差异，包括它们的容错属性（请参阅第 5 章）和并发处理（请参阅 第 7 章）。在本章中，我们将仅关注数据模型的差异。

There are many differences to consider when comparing relational databases to document databases, including their fault-tolerance properties (see Chapter 5) and handling of concurrency (see Chapter 7). In this chapter, we will concentrate only on the differences in the data model.

支持文档数据模型的主要论点是模式灵活性、由于局部性而带来的更好的性能，以及对于某些应用程序来说它更接近应用程序使用的数据结构。关系模型通过为连接、多对一和多对多关系提供更好的支持来应对。

The main arguments in favor of the document data model are schema flexibility, better performance due to locality, and that for some applications it is closer to the data structures used by the application. The relational model counters by providing better support for joins, and many-to-one and many-to-many relationships.

if (user && user.name && !user.first_name) {
    // Documents written before Dec 8, 2013 don't have first_name
    user.first_name = user.name.split(" ")[0];
}

if (user && user.name && !user.first_name) {
    // Documents written before Dec 8, 2013 don't have first_name
    user.first_name = user.name.split(" ")[0];
}

ALTER TABLE users ADD COLUMN first_name text;
UPDATE users SET first_name = split_part(name, ' ', 1);      -- PostgreSQL
UPDATE users SET first_name = substring_index(name, ' ', 1);      -- MySQL

ALTER TABLE users ADD COLUMN first_name text;
UPDATE users SET first_name = split_part(name, ' ', 1);      -- PostgreSQL
UPDATE users SET first_name = substring_index(name, ' ', 1);      -- MySQL

Web 上的声明式查询

Declarative Queries on the Web

声明性查询语言的优点不仅仅限于数据库。为了说明这一点，让我们在完全不同的环境（Web 浏览器）中比较声明式方法和命令式方法。

The advantages of declarative query languages are not limited to just databases. To illustrate the point, let’s compare declarative and imperative approaches in a completely different environment: a web browser.

假设您有一个有关海洋动物的网站。用户当前正在查看有关鲨鱼的页面，因此您将导航项“Sharks”标记为当前选定的，如下所示：

Say you have a website about animals in the ocean. The user is currently viewing the page on sharks, so you mark the navigation item “Sharks” as currently selected, like this:

<ul>
    <li class="selected"> 
        <p>Sharks</p> 
        <ul>
            <li>Great White Shark</li>
            <li>Tiger Shark</li>
            <li>Hammerhead Shark</li>
        </ul>
    </li>
    <li>
        <p>Whales</p>
        <ul>
            <li>Blue Whale</li>
            <li>Humpback Whale</li>
            <li>Fin Whale</li>
        </ul>
    </li>
</ul>

<ul>
    <li class="selected"> 
        <p>Sharks</p> 
        <ul>
            <li>Great White Shark</li>
            <li>Tiger Shark</li>
            <li>Hammerhead Shark</li>
        </ul>
    </li>
    <li>
        <p>Whales</p>
        <ul>
            <li>Blue Whale</li>
            <li>Humpback Whale</li>
            <li>Fin Whale</li>
        </ul>
    </li>
</ul>

所选项目标有 CSS 类"selected"。

The selected item is marked with the CSS class "selected".

<p>Sharks</p>是当前所选页面的标题。

<p>Sharks</p> is the title of the currently selected page.

现在假设您希望当前所选页面的标题具有蓝色背景，以便在视觉上突出显示。这很简单，使用 CSS：

Now say you want the title of the currently selected page to have a blue background, so that it is visually highlighted. This is easy, using CSS:

li.selected > p {
    background-color: blue;
}

li.selected > p {
    background-color: blue;
}

这里 CSS 选择器li.selected > p声明了我们要应用蓝色样式的元素模式：即，<p>其直接父级是<li>CSS 类为 的元素的所有元素selected。<p>Sharks</p>示例中的元素与此模式匹配，但<p>Whales</p> 不匹配，因为<li>其父元素缺少class="selected"。

Here the CSS selector li.selected > p declares the pattern of elements to which we want to apply the blue style: namely, all <p> elements whose direct parent is an <li> element with a CSS class of selected. The element <p>Sharks</p> in the example matches this pattern, but <p>Whales</p> does not match because its <li> parent lacks class="selected".

如果您使用 XSL 而不是 CSS，您可以执行类似的操作：

If you were using XSL instead of CSS, you could do something similar:

<xsl:template match="li[@class='selected']/p">
    <fo:block background-color="blue">
        <xsl:apply-templates/>
    </fo:block>
</xsl:template>

<xsl:template match="li[@class='selected']/p">
    <fo:block background-color="blue">
        <xsl:apply-templates/>
    </fo:block>
</xsl:template>

这里，XPath 表达式li[@class='selected']/p相当于li.selected > p前面示例中的 CSS 选择器。CSS 和 XSL 的共同点是它们都是用于指定文档样式的声明性语言。

Here, the XPath expression li[@class='selected']/p is equivalent to the CSS selector li.selected > p in the previous example. What CSS and XSL have in common is that they are both declarative languages for specifying the styling of a document.

想象一下，如果您必须使用命令式方法，生活会是什么样子。在 JavaScript 中，使用核心文档对象模型 (DOM) API，结果可能如下所示：

Imagine what life would be like if you had to use an imperative approach. In JavaScript, using the core Document Object Model (DOM) API, the result might look something like this:

var liElements = document.getElementsByTagName("li");
for (var i = 0; i < liElements.length; i++) {
    if (liElements[i].className === "selected") {
        var children = liElements[i].childNodes;
        for (var j = 0; j < children.length; j++) {
            var child = children[j];
            if (child.nodeType === Node.ELEMENT_NODE && child.tagName === "P") {
                child.setAttribute("style", "background-color: blue");
            }
        }
    }
}

var liElements = document.getElementsByTagName("li");
for (var i = 0; i < liElements.length; i++) {
    if (liElements[i].className === "selected") {
        var children = liElements[i].childNodes;
        for (var j = 0; j < children.length; j++) {
            var child = children[j];
            if (child.nodeType === Node.ELEMENT_NODE && child.tagName === "P") {
                child.setAttribute("style", "background-color: blue");
            }
        }
    }
}

这段 JavaScript 强制将元素设置<p>Sharks</p>为蓝色背景，但代码很糟糕。它不仅比 CSS 和 XSL 等价物更长、更难理解，而且还存在一些严重的问题：

This JavaScript imperatively sets the element <p>Sharks</p> to have a blue background, but the code is awful. Not only is it much longer and harder to understand than the CSS and XSL equivalents, but it also has some serious problems:

• 如果selected删除该类（例如，因为用户单击不同的页面），则即使重新运行代码，蓝色也不会被删除，因此该项目将保持突出显示状态，直到重新加载整个页面。使用CSS，浏览器会自动检测li.selected > p 规则何时不再适用，并在selected删除类后立即删除蓝色背景。

• If the selected class is removed (e.g., because the user clicks a different page), the blue color won’t be removed, even if the code is rerun—and so the item will remain highlighted until the entire page is reloaded. With CSS, the browser automatically detects when the li.selected > p rule no longer applies and removes the blue background as soon as the selected class is removed.

• 如果您想利用新的 API，例如document.getElementsByClassName("selected") 或什至document.evaluate()（这可能会提高性能），您必须重写代码。另一方面，浏览器供应商可以在不破坏兼容性的情况下提高 CSS 和 XPath 的性能。

• If you want to take advantage of a new API, such as document.getElementsByClassName("selected") or even document.evaluate()—which may improve performance—you have to rewrite the code. On the other hand, browser vendors can improve the performance of CSS and XPath without breaking compatibility.

在 Web 浏览器中，使用声明性 CSS 样式比在 JavaScript 中命令式操作样式要好得多。同样，在数据库中，SQL 等声明式查询语言比命令式查询 API 好得多。^六

In a web browser, using declarative CSS styling is much better than manipulating styles imperatively in JavaScript. Similarly, in databases, declarative query languages like SQL turned out to be much better than imperative query APIs.^vi

MapReduce查询

MapReduce Querying

MapReduce是一种用于跨多台机器批量处理大量数据的编程模型，由 Google 推广[ 33 ]。一些 NoSQL 数据存储（包括 MongoDB 和 CouchDB）支持有限形式的 MapReduce，作为跨多个文档执行只读查询的机制。

MapReduce is a programming model for processing large amounts of data in bulk across many machines, popularized by Google [33]. A limited form of MapReduce is supported by some NoSQL datastores, including MongoDB and CouchDB, as a mechanism for performing read-only queries across many documents.

一般而言，MapReduce 在第 10 章中有更详细的描述。现在，我们将简要讨论 MongoDB 对模型的使用。

MapReduce in general is described in more detail in Chapter 10. For now, we’ll just briefly discuss MongoDB’s use of the model.

MapReduce 既不是声明式查询语言，也不是完全命令式查询 API，而是介于两者之间：查询的逻辑用代码片段表示，由处理框架重复调用。它基于许多函数式编程语言中存在的map(也称为collect) 和reduce(也称为fold或) 函数。inject

MapReduce is neither a declarative query language nor a fully imperative query API, but somewhere in between: the logic of the query is expressed with snippets of code, which are called repeatedly by the processing framework. It is based on the map (also known as collect) and reduce (also known as fold or inject) functions that exist in many functional programming languages.

举个例子，假设您是一名海洋生物学家，每次看到海洋中的动物时，您都会在数据库中添加一条观察记录。现在您想要生成一份报告，说明您每月看到的鲨鱼数量。

To give an example, imagine you are a marine biologist, and you add an observation record to your database every time you see animals in the ocean. Now you want to generate a report saying how many sharks you have sighted per month.

在 PostgreSQL 中，您可以像这样表达该查询：

In PostgreSQL you might express that query like this:

SELECT date_trunc('month', observation_timestamp) AS observation_month, 
       sum(num_animals) AS total_animals
FROM observations
WHERE family = 'Sharks'
GROUP BY observation_month;

SELECT date_trunc('month', observation_timestamp) AS observation_month, 
       sum(num_animals) AS total_animals
FROM observations
WHERE family = 'Sharks'
GROUP BY observation_month;

该date_trunc('month', timestamp)函数确定包含 的日历月timestamp，并返回表示该月开始的另一个时间戳。换句话说，它将时间戳向下舍入到最近的月份。

The date_trunc('month', timestamp) function determines the calendar month containing timestamp, and returns another timestamp representing the beginning of that month. In other words, it rounds a timestamp down to the nearest month.

该查询首先过滤观测值，仅显示科中的物种Sharks，然后按观测值发生的日历月份对观测值进行分组，最后将该月所有观测值中看到的动物数量相加。

This query first filters the observations to only show species in the Sharks family, then groups the observations by the calendar month in which they occurred, and finally adds up the number of animals seen in all observations in that month.

同样的情况也可以用 MongoDB 的 MapReduce 功能来表达，如下所示：

The same can be expressed with MongoDB’s MapReduce feature as follows:

db.observations.mapReduce(
    function map() { 
        var year  = this.observationTimestamp.getFullYear();
        var month = this.observationTimestamp.getMonth() + 1;
        emit(year + "-" + month, this.numAnimals); 
    },
    function reduce(key, values) { 
        return Array.sum(values); 
    },
    {
        query: { family: "Sharks" }, 
        out: "monthlySharkReport" 
    }
);

db.observations.mapReduce(
    function map() { 
        var year  = this.observationTimestamp.getFullYear();
        var month = this.observationTimestamp.getMonth() + 1;
        emit(year + "-" + month, this.numAnimals); 
    },
    function reduce(key, values) { 
        return Array.sum(values); 
    },
    {
        query: { family: "Sharks" }, 
        out: "monthlySharkReport" 
    }
);

可以以声明方式指定仅考虑鲨鱼种类的过滤器（这是 MapReduce 的 MongoDB 特定扩展）。

The filter to consider only shark species can be specified declaratively (this is a MongoDB-specific extension to MapReduce).

对于每个匹配的文档， JavaScript 函数map都会被调用一次query，并且 this设置为文档对象。

The JavaScript function map is called once for every document that matches query, with this set to the document object.

该map函数发出一个键（由年和月组成的字符串，例如"2013-12"或 "2014-1"）和一个值（该观察中的动物数量）。

The map function emits a key (a string consisting of year and month, such as "2013-12" or "2014-1") and a value (the number of animals in that observation).

发出的键值对map按键分组。对于具有相同键（即相同月份和年份）的所有键值对，该reduce函数被调用一次。

The key-value pairs emitted by map are grouped by key. For all key-value pairs with the same key (i.e., the same month and year), the reduce function is called once.

该reduce函数将特定月份所有观察到的动物数量相加。

The reduce function adds up the number of animals from all observations in a particular month.

最终输出写入集合中monthlySharkReport。

The final output is written to the collection monthlySharkReport.

例如，假设observations集合包含这两个文档：

For example, say the observations collection contains these two documents:

{
    observationTimestamp: Date.parse("Mon, 25 Dec 1995 12:34:56 GMT"),
    family:     "Sharks",
    species:    "Carcharodon carcharias",
    numAnimals: 3
}
{
    observationTimestamp: Date.parse("Tue, 12 Dec 1995 16:17:18 GMT"),
    family:     "Sharks",
    species:    "Carcharias taurus",
    numAnimals: 4
}

{
    observationTimestamp: Date.parse("Mon, 25 Dec 1995 12:34:56 GMT"),
    family:     "Sharks",
    species:    "Carcharodon carcharias",
    numAnimals: 3
}
{
    observationTimestamp: Date.parse("Tue, 12 Dec 1995 16:17:18 GMT"),
    family:     "Sharks",
    species:    "Carcharias taurus",
    numAnimals: 4
}

该map函数将为每个文档调用一次，结果是 emit("1995-12", 3)和 emit("1995-12", 4)。随后，该reduce函数将被调用并reduce("1995-12", [3, 4])返回 7。

The map function would be called once for each document, resulting in emit("1995-12", 3) and emit("1995-12", 4). Subsequently, the reduce function would be called with reduce("1995-12", [3, 4]), returning 7.

和函数在允许执行的操作方面受到一定限制map。reduce它们必须是 纯函数，这意味着它们仅使用传递给它们的数据作为输入，它们不能执行额外的数据库查询，并且不能有任何副作用。这些限制允许数据库在任何地方、以任何顺序运行这些函数，并在失败时重新运行它们。然而，它们仍然很强大：它们可以解析字符串、调用库函数、执行计算等等。

The map and reduce functions are somewhat restricted in what they are allowed to do. They must be pure functions, which means they only use the data that is passed to them as input, they cannot perform additional database queries, and they must not have any side effects. These restrictions allow the database to run the functions anywhere, in any order, and rerun them on failure. However, they are nevertheless powerful: they can parse strings, call library functions, perform calculations, and more.

MapReduce 是一个相当低级的编程模型，用于在机器集群上分布式执行。像 SQL 这样的高级查询语言可以实现为 MapReduce 操作的管道（参见第 10 章），但是也有许多不使用 MapReduce 的 SQL 分布式实现。请注意，SQL 中没有任何内容限制它在单台机器上运行，并且 MapReduce 并不垄断分布式查询执行。

MapReduce is a fairly low-level programming model for distributed execution on a cluster of machines. Higher-level query languages like SQL can be implemented as a pipeline of MapReduce operations (see Chapter 10), but there are also many distributed implementations of SQL that don’t use MapReduce. Note there is nothing in SQL that constrains it to running on a single machine, and MapReduce doesn’t have a monopoly on distributed query execution.

能够在查询中间使用 JavaScript 代码对于高级查询来说是一个很棒的功能，但它不仅限于 MapReduce — 一些 SQL 数据库也可以使用 JavaScript 函数进行扩展 [34 ]。

Being able to use JavaScript code in the middle of a query is a great feature for advanced queries, but it’s not limited to MapReduce—some SQL databases can be extended with JavaScript functions too [34].

MapReduce 的一个可用性问题是您必须编写两个仔细协调的 JavaScript 函数，这通常比编写单个查询更困难。此外，声明性查询语言为查询优化器提供了更多提高查询性能的机会。由于这些原因，MongoDB 2.2 添加了对称为聚合管道的声明式查询语言的支持 [ 9 ]。在这种语言中，相同的鲨鱼计数查询如下所示：

A usability problem with MapReduce is that you have to write two carefully coordinated JavaScript functions, which is often harder than writing a single query. Moreover, a declarative query language offers more opportunities for a query optimizer to improve the performance of a query. For these reasons, MongoDB 2.2 added support for a declarative query language called the aggregation pipeline [9]. In this language, the same shark-counting query looks like this:

db.observations.aggregate([
    { $match: { family: "Sharks" } },
    { $group: {
        _id: {
            year:  { $year:  "$observationTimestamp" },
            month: { $month: "$observationTimestamp" }
        },
        totalAnimals: { $sum: "$numAnimals" }
    } }
]);

db.observations.aggregate([
    { $match: { family: "Sharks" } },
    { $group: {
        _id: {
            year:  { $year:  "$observationTimestamp" },
            month: { $month: "$observationTimestamp" }
        },
        totalAnimals: { $sum: "$numAnimals" }
    } }
]);

聚合管道语言在表达能力上类似于 SQL 的子集，但它使用基于 JSON 的语法，而不是 SQL 的英语句子式语法；差异也许是品味问题。这个故事的寓意是，NoSQL 系统可能会发现自己意外地重新发明了 SQL，尽管是伪装的。

The aggregation pipeline language is similar in expressiveness to a subset of SQL, but it uses a JSON-based syntax rather than SQL’s English-sentence-style syntax; the difference is perhaps a matter of taste. The moral of the story is that a NoSQL system may find itself accidentally reinventing SQL, albeit in disguise.

属性图

Property Graphs

在属性图模型中，每个顶点由以下部分组成：

In the property graph model, each vertex consists of:

• 唯一标识符

• A unique identifier

• 一组出边

• A set of outgoing edges

• 一组传入边

• A set of incoming edges

• 属性集合（键值对）

• A collection of properties (key-value pairs)

每条边由以下部分组成：

Each edge consists of:

• 唯一标识符

• A unique identifier

• 边开始的顶点（尾部顶点）

• The vertex at which the edge starts (the tail vertex)

• 边结束的顶点（头顶点）

• The vertex at which the edge ends (the head vertex)

• 描述两个顶点之间关系类型的标签

• A label to describe the kind of relationship between the two vertices

• 属性集合（键值对）

• A collection of properties (key-value pairs)

您可以将图存储视为由两个关系表组成，一张用于顶点，一张用于边，如示例 2-2 所示（此模式使用 PostgreSQLjson数据类型来存储每个顶点或边的属性）。为每条边存储头尾顶点；如果您想要某个顶点的入边或出边集合，可以分别edges通过 head_vertex或查询表tail_vertex。

You can think of a graph store as consisting of two relational tables, one for vertices and one for edges, as shown in Example 2-2 (this schema uses the PostgreSQL json datatype to store the properties of each vertex or edge). The head and tail vertex are stored for each edge; if you want the set of incoming or outgoing edges for a vertex, you can query the edges table by head_vertex or tail_vertex, respectively.

CREATE TABLE vertices (
    vertex_id   integer PRIMARY KEY,
    properties  json
);

CREATE TABLE edges (
    edge_id     integer PRIMARY KEY,
    tail_vertex integer REFERENCES vertices (vertex_id),
    head_vertex integer REFERENCES vertices (vertex_id),
    label       text,
    properties  json
);

CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

CREATE TABLE vertices (
    vertex_id   integer PRIMARY KEY,
    properties  json
);

CREATE TABLE edges (
    edge_id     integer PRIMARY KEY,
    tail_vertex integer REFERENCES vertices (vertex_id),
    head_vertex integer REFERENCES vertices (vertex_id),
    label       text,
    properties  json
);

CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

该模型的一些重要方面是：

Some important aspects of this model are:

1. 任何顶点都可以有一条边将其与任何其他顶点连接起来。没有模式限制哪些类型的事物可以关联或不可以关联。

2. Any vertex can have an edge connecting it with any other vertex. There is no schema that restricts which kinds of things can or cannot be associated.

3. 给定任何顶点，您可以有效地找到其传入边和传出边，从而 向前和向后遍历图，即沿着通过顶点链的路径。（这就是示例 2-2tail_vertex在和列上都有索引的原因head_vertex 。）

4. Given any vertex, you can efficiently find both its incoming and its outgoing edges, and thus traverse the graph—i.e., follow a path through a chain of vertices—both forward and backward. (That’s why Example 2-2 has indexes on both the tail_vertex and head_vertex columns.)

5. 通过对不同类型的关系使用不同的标签，您可以在单个图表中存储多种不同类型的信息，同时仍然保持干净的数据模型。

6. By using different labels for different kinds of relationships, you can store several different kinds of information in a single graph, while still maintaining a clean data model.

这些功能为图的数据建模提供了很大的灵活性，如图 2-5所示。该图显示了一些在传统关系模式中难以表达的内容，例如不同国家的不同类型的区域结构（法国有省和地区，而美国有县和州），历史的怪癖，例如国中之国（暂时忽略主权国家和民族的复杂性），以及不同粒度的数据（露西当前居住地被指定为城市，而她的出生地仅在州级别被指定）。

Those features give graphs a great deal of flexibility for data modeling, as illustrated in Figure 2-5. The figure shows a few things that would be difficult to express in a traditional relational schema, such as different kinds of regional structures in different countries (France has départements and régions, whereas the US has counties and states), quirks of history such as a country within a country (ignoring for now the intricacies of sovereign states and nations), and varying granularity of data (Lucy’s current residence is specified as a city, whereas her place of birth is specified only at the level of a state).

您可以想象将图表扩展为还包括有关露西和阿兰或其他人的许多其他事实。例如，您可以使用它来指示他们对任何食物过敏（通过为每种过敏原引入一个顶点，并在人和过敏原之间引入一条边来指示过敏），并将过敏原与一组顶点联系起来，这些顶点显示哪些过敏原食物中含有哪些物质。然后您可以编写一个查询来找出每个人吃什么是安全的。 图有利于可进化性：当您向应用程序添加功能时，可以轻松扩展图以适应应用程序数据结构的变化。

You could imagine extending the graph to also include many other facts about Lucy and Alain, or other people. For instance, you could use it to indicate any food allergies they have (by introducing a vertex for each allergen, and an edge between a person and an allergen to indicate an allergy), and link the allergens with a set of vertices that show which foods contain which substances. Then you could write a query to find out what is safe for each person to eat. Graphs are good for evolvability: as you add features to your application, a graph can easily be extended to accommodate changes in your application’s data structures.

Cypher 查询语言

The Cypher Query Language

Cypher是一种属性图的声明性查询语言，为 Neo4j 图形数据库创建[ 37 ]。（它以电影《黑客帝国》中的一个角色命名 ，与密码学中的密码无关[ 38 ]。）

Cypher is a declarative query language for property graphs, created for the Neo4j graph database [37]. (It is named after a character in the movie The Matrix and is not related to ciphers in cryptography [38].)

示例 2-3显示了将图 2-5左侧部分插入 到图形数据库中的 Cypher 查询。图表的其余部分可以类似地添加，并且为了可读性而被省略。每个顶点都被赋予一个符号名称，例如USA或Idaho，查询的其他部分可以使用这些名称在顶点之间创建边，使用箭头表示法： (Idaho) -[:WITHIN]-> (USA)创建一条标记为 的边WITHIN，作为Idaho尾节点和USA 头节点。

Example 2-3 shows the Cypher query to insert the lefthand portion of Figure 2-5 into a graph database. The rest of the graph can be added similarly and is omitted for readability. Each vertex is given a symbolic name like USA or Idaho, and other parts of the query can use those names to create edges between the vertices, using an arrow notation: (Idaho) -[:WITHIN]-> (USA) creates an edge labeled WITHIN, with Idaho as the tail node and USA as the head node.

CREATE
  (NAmerica:Location {name:'North America', type:'continent'}),
  (USA:Location      {name:'United States', type:'country'  }),
  (Idaho:Location    {name:'Idaho',         type:'state'    }),
  (Lucy:Person       {name:'Lucy' }),
  (Idaho) -[:WITHIN]->  (USA)  -[:WITHIN]-> (NAmerica),
  (Lucy)  -[:BORN_IN]-> (Idaho)

CREATE
  (NAmerica:Location {name:'North America', type:'continent'}),
  (USA:Location      {name:'United States', type:'country'  }),
  (Idaho:Location    {name:'Idaho',         type:'state'    }),
  (Lucy:Person       {name:'Lucy' }),
  (Idaho) -[:WITHIN]->  (USA)  -[:WITHIN]-> (NAmerica),
  (Lucy)  -[:BORN_IN]-> (Idaho)

当图 2-5的所有顶点和边都添加到数据库中时，我们可以开始提出有趣的问题：例如，查找所有从美国移民到欧洲的人的姓名。更准确地说，这里我们想要找到所有具有BORN_IN到美国境内某个位置的边以及LIVING_IN到欧洲境内某个位置的边的顶点，并返回 name每个顶点的属性。

When all the vertices and edges of Figure 2-5 are added to the database, we can start asking interesting questions: for example, find the names of all the people who emigrated from the United States to Europe. To be more precise, here we want to find all the vertices that have a BORN_IN edge to a location within the US, and also a LIVING_IN edge to a location within Europe, and return the name property of each of those vertices.

示例 2-4显示了如何在 Cypher 中表达该查询。子句中使用相同的箭头表示法 MATCH来查找图中的模式：(person) -[:BORN_IN]-> ()匹配由标记为 的边相关的任意两个顶点BORN_IN。该边的尾部顶点绑定到变量person，而头顶点未命名。

Example 2-4 shows how to express that query in Cypher. The same arrow notation is used in a MATCH clause to find patterns in the graph: (person) -[:BORN_IN]-> () matches any two vertices that are related by an edge labeled BORN_IN. The tail vertex of that edge is bound to the variable person, and the head vertex is left unnamed.

MATCH
  (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
  (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

MATCH
  (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
  (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

该查询可以解读如下：

The query can be read as follows:

person找到满足以下两个条件的任何顶点（称为）：

1. person有BORN_IN到某个顶点的出边。从该顶点开始，您可以遵循一系列传出边，WITHIN直到最终到达类型为 的顶点Location，其name 属性等于"United States"。

2. 同一个person顶点也有一个出LIVES_IN边。沿着该边，然后是一系列传出边WITHIN，您最终到达类型为 的顶点Location，其name 属性等于"Europe"。

对于每个这样的person顶点，返回name属性。

Find any vertex (call it person) that meets both of the following conditions:

1. person has an outgoing BORN_IN edge to some vertex. From that vertex, you can follow a chain of outgoing WITHIN edges until eventually you reach a vertex of type Location, whose name property is equal to "United States".

2. That same person vertex also has an outgoing LIVES_IN edge. Following that edge, and then a chain of outgoing WITHIN edges, you eventually reach a vertex of type Location, whose name property is equal to "Europe".

For each such person vertex, return the name property.

有多种可能的执行查询的方法。这里给出的描述建议您首先扫描数据库中的所有人员，检查每个人的出生地和居住地，然后仅返回符合条件的人员。

There are several possible ways of executing the query. The description given here suggests that you start by scanning all the people in the database, examine each person’s birthplace and residence, and return only those people who meet the criteria.

但同样地，您可以从两个Location顶点开始并向后进行。如果该name属性有一个索引，您可能可以有效地找到代表美国和欧洲的两个顶点。然后，您可以通过跟踪所有传入边来分别查找美国和欧洲的所有位置（州、地区、城市等）WITHIN。最后，您可以寻找可以通过位置顶点之一的传入BORN_IN或边找到的人。LIVES_IN

But equivalently, you could start with the two Location vertices and work backward. If there is an index on the name property, you can probably efficiently find the two vertices representing the US and Europe. Then you can proceed to find all locations (states, regions, cities, etc.) in the US and Europe respectively by following all incoming WITHIN edges. Finally, you can look for people who can be found through an incoming BORN_IN or LIVES_IN edge at one of the location vertices.

正如声明性查询语言的典型情况一样，您在编写查询时不需要指定此类执行细节：查询优化器会自动选择预测最有效的策略，因此您可以继续编写其余的部分你的申请。

As is typical for a declarative query language, you don’t need to specify such execution details when writing the query: the query optimizer automatically chooses the strategy that is predicted to be the most efficient, so you can get on with writing the rest of your application.

SQL 中的图形查询

Graph Queries in SQL

示例 2-2表明图形数据可以在关系数据库中表示。但是如果我们把图数据放在关系结构中，我们是否也可以使用SQL来查询它呢？

Example 2-2 suggested that graph data can be represented in a relational database. But if we put graph data in a relational structure, can we also query it using SQL?

答案是肯定的，但有一定难度。在关系数据库中，您通常预先知道查询中需要哪些联接。在图查询中，在找到要查找的顶点之前，您可能需要遍历可变数量的边，也就是说，连接的数量并不是预先固定的。

The answer is yes, but with some difficulty. In a relational database, you usually know in advance which joins you need in your query. In a graph query, you may need to traverse a variable number of edges before you find the vertex you’re looking for—that is, the number of joins is not fixed in advance.

在我们的示例中，这发生在() -[:WITHIN*0..]-> ()Cypher 查询的规则中。人的 LIVES_IN边缘可以指向任何类型的位置：街道、城市、区、地区、州等。城市可以是地区WITHIN、地区、州WITHIN、州WITHIN、国家等。LIVES_IN边缘可以是直接指向您要查找的位置顶点，或者它可能是位置层次结构中删除的多个级别。

In our example, that happens in the () -[:WITHIN*0..]-> () rule in the Cypher query. A person’s LIVES_IN edge may point at any kind of location: a street, a city, a district, a region, a state, etc. A city may be WITHIN a region, a region WITHIN a state, a state WITHIN a country, etc. The LIVES_IN edge may point directly at the location vertex you’re looking for, or it may be several levels removed in the location hierarchy.

在 Cypher 中，:WITHIN*0..非常简洁地表达了这一事实：它的意思是“沿着一条WITHIN边，零次或多次”。它就像*正则表达式中的运算符。

In Cypher, :WITHIN*0.. expresses that fact very concisely: it means “follow a WITHIN edge, zero or more times.” It is like the * operator in a regular expression.

从 SQL:1999 开始，查询中的可变长度遍历路径的想法可以使用称为递归公用表表达式（WITH RECURSIVE语法）的东西来表达。 示例 2-5显示了使用此技术（在 PostgreSQL、IBM DB2、Oracle 和 SQL Server 中支持）的 SQL 中表达的相同查询（查找从美国移民到欧洲的人的姓名）。然而，与 Cypher 相比，其语法非常笨拙。

Since SQL:1999, this idea of variable-length traversal paths in a query can be expressed using something called recursive common table expressions (the WITH RECURSIVE syntax). Example 2-5 shows the same query—finding the names of people who emigrated from the US to Europe—expressed in SQL using this technique (supported in PostgreSQL, IBM DB2, Oracle, and SQL Server). However, the syntax is very clumsy in comparison to Cypher.

WITH RECURSIVE

  -- in_usa is the set of vertex IDs of all locations within the United States
  in_usa(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'United States' 
    UNION
      SELECT edges.tail_vertex FROM edges 
        JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
        WHERE edges.label = 'within'
  ),

  -- in_europe is the set of vertex IDs of all locations within Europe
  in_europe(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'Europe' 
    UNION
      SELECT edges.tail_vertex FROM edges
        JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
        WHERE edges.label = 'within'
  ),

  -- born_in_usa is the set of vertex IDs of all people born in the US
  born_in_usa(vertex_id) AS ( 
    SELECT edges.tail_vertex FROM edges
      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
      WHERE edges.label = 'born_in'
  ),

  -- lives_in_europe is the set of vertex IDs of all people living in Europe
  lives_in_europe(vertex_id) AS ( 
    SELECT edges.tail_vertex FROM edges
      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
      WHERE edges.label = 'lives_in'
  )

SELECT vertices.properties->>'name'
FROM vertices
-- join to find those people who were both born in the US *and* live in Europe
JOIN born_in_usa     ON vertices.vertex_id = born_in_usa.vertex_id 
JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

WITH RECURSIVE

  -- in_usa is the set of vertex IDs of all locations within the United States
  in_usa(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'United States' 
    UNION
      SELECT edges.tail_vertex FROM edges 
        JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
        WHERE edges.label = 'within'
  ),

  -- in_europe is the set of vertex IDs of all locations within Europe
  in_europe(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'Europe' 
    UNION
      SELECT edges.tail_vertex FROM edges
        JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
        WHERE edges.label = 'within'
  ),

  -- born_in_usa is the set of vertex IDs of all people born in the US
  born_in_usa(vertex_id) AS ( 
    SELECT edges.tail_vertex FROM edges
      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
      WHERE edges.label = 'born_in'
  ),

  -- lives_in_europe is the set of vertex IDs of all people living in Europe
  lives_in_europe(vertex_id) AS ( 
    SELECT edges.tail_vertex FROM edges
      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
      WHERE edges.label = 'lives_in'
  )

SELECT vertices.properties->>'name'
FROM vertices
-- join to find those people who were both born in the US *and* live in Europe
JOIN born_in_usa     ON vertices.vertex_id = born_in_usa.vertex_id 
JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

如果相同的查询可以用一种查询语言编写 4 行，但用另一种查询语言需要 29 行，这就表明不同的数据模型是为了满足不同的用例而设计的。选择适合您的应用程序的数据模型非常重要。

If the same query can be written in 4 lines in one query language but requires 29 lines in another, that just shows that different data models are designed to satisfy different use cases. It’s important to pick a data model that is suitable for your application.

三重存储和 SPARQL

Triple-Stores and SPARQL

三元存储模型基本上等同于属性图模型，使用不同的词语来描述相同的想法。尽管如此，它还是值得讨论的，因为有多种用于三重存储的工具和语言，可以为您构建应用程序的工具箱提供有价值的补充。

The triple-store model is mostly equivalent to the property graph model, using different words to describe the same ideas. It is nevertheless worth discussing, because there are various tools and languages for triple-stores that can be valuable additions to your toolbox for building applications.

在三元组存储中，所有信息都以非常简单的三部分语句的形式存储：（主语、谓语、宾语）。例如，在三元组（Jim、likes、bananas）中，Jim是主语，likes是谓语（动词），bananas是宾语。

In a triple-store, all information is stored in the form of very simple three-part statements: (subject, predicate, object). For example, in the triple (Jim, likes, bananas), Jim is the subject, likes is the predicate (verb), and bananas is the object.

三元组的主语相当于图中的一个顶点。该对象是以下两件事之一：

The subject of a triple is equivalent to a vertex in a graph. The object is one of two things:

1. 原始数据类型中的值，例如字符串或数字。在这种情况下，三元组的谓词和宾语相当于主语顶点上属性的键和值。例如，( lucy , age , 33 )就像一个lucy具有properties的 顶点{"age":33}。

2. A value in a primitive datatype, such as a string or a number. In that case, the predicate and object of the triple are equivalent to the key and value of a property on the subject vertex. For example, (lucy, age, 33) is like a vertex lucy with properties {"age":33}.

3. 图中的另一个顶点。在这种情况下，谓词是图中的边，主语是尾部顶点，宾语是头顶点。例如，在 ( lucy , MarriedTo , alain ) 中，主语和宾语lucy和alain都是顶点，谓词MarriedTo是连接它们的边的标签。

4. Another vertex in the graph. In that case, the predicate is an edge in the graph, the subject is the tail vertex, and the object is the head vertex. For example, in (lucy, marriedTo, alain) the subject and object lucy and alain are both vertices, and the predicate marriedTo is the label of the edge that connects them.

示例 2-6显示了与示例 2-3中相同的数据，以称为Turtle的格式编写为三元组，这是Notation3 ( N3 ) [ 39 ]的子集。

Example 2-6 shows the same data as in Example 2-3, written as triples in a format called Turtle, a subset of Notation3 (N3) [39].

@前缀：<瓮：示例：>。
_：露西：人。
_：露西：名字“露西”。
_：露西：出生于_：爱达荷州。
_：爱达荷州 a：位置。
_:idaho :名称“爱达荷”。
_：爱达荷州：输入“州”。
_：爱达荷州：_：美国境内。
_：美国 a：位置。
_:usa :名称“美国”。
_:美国：输入“国家”。
_：美国：_：美洲境内。
_:namerica :位置。
_:namerica :名称“北美”。
_:namerica :输入“大陆”。

@prefix : <urn:example:>.
_:lucy     a       :Person.
_:lucy     :name   "Lucy".
_:lucy     :bornIn _:idaho.
_:idaho    a       :Location.
_:idaho    :name   "Idaho".
_:idaho    :type   "state".
_:idaho    :within _:usa.
_:usa      a       :Location.
_:usa      :name   "United States".
_:usa      :type   "country".
_:usa      :within _:namerica.
_:namerica a       :Location.
_:namerica :name   "North America".
_:namerica :type   "continent".

在此示例中，图的顶点被写为。该名称在该文件之外没有任何含义；它存在只是因为否则我们不知道哪些三元组引用同一个顶点。当谓词表示一条边时，对象是一个顶点，如 中。当谓词是属性时，对象是字符串文字，如 中所示。_:someName_:idaho :within _:usa_:usa :name "United States"

In this example, vertices of the graph are written as _:someName. The name doesn’t mean anything outside of this file; it exists only because we otherwise wouldn’t know which triples refer to the same vertex. When the predicate represents an edge, the object is a vertex, as in _:idaho :within _:usa. When the predicate is a property, the object is a string literal, as in _:usa :name "United States".

一遍又一遍地重复同一主题是相当重复的，但幸运的是，您可以使用分号来表达同一主题的多个内容。这使得 Turtle 格式非常漂亮且可读：参见示例 2-7。

It’s quite repetitive to repeat the same subject over and over again, but fortunately you can use semicolons to say multiple things about the same subject. This makes the Turtle format quite nice and readable: see Example 2-7.

@前缀：<瓮：示例：>。
_：露西一个：人；：姓名“露西”；：出生于_：爱达荷州。
_：爱达荷州：位置；：名称“爱达荷州”；：输入“状态”；：在_：美国境内。
_：美国 a ：位置；：名称“美国”；：输入“国家”；：在_：美洲内。
_: 美洲 a : 位置; ：名称“北美”；：输入“大陆”。

@prefix : <urn:example:>.
_:lucy     a :Person;   :name "Lucy";          :bornIn _:idaho.
_:idaho    a :Location; :name "Idaho";         :type "state";   :within _:usa.
_:usa      a :Location; :name "United States"; :type "country"; :within _:namerica.
_:namerica a :Location; :name "North America"; :type "continent".

<rdf:RDF xmlns="urn:example:"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">

  <Location rdf:nodeID="idaho">
    <name>爱达荷州</name>
    <type>美国国家北美洲大陆</type>
    <within>
      <Location rdf:nodeID="usa">
        <name>_</name>
        <type></type>
        <within>
          <Location rdf:nodeID="namerica">
            <name></name>
            <type></type>
          </Location>
        </within>
      </Location>
    </within>
  </Location>

  <Person rdf:nodeID="lucy">
    <name>露西</name>
    <bornIn rdf:nodeID="idaho"/>
  </Person>
</rdf:RDF>

<rdf:RDF xmlns="urn:example:"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">

  <Location rdf:nodeID="idaho">
    <name>Idaho</name>
    <type>state</type>
    <within>
      <Location rdf:nodeID="usa">
        <name>United States</name>
        <type>country</type>
        <within>
          <Location rdf:nodeID="namerica">
            <name>North America</name>
            <type>continent</type>
          </Location>
        </within>
      </Location>
    </within>
  </Location>

  <Person rdf:nodeID="lucy">
    <name>Lucy</name>
    <bornIn rdf:nodeID="idaho"/>
  </Person>
</rdf:RDF>

PREFIX : <urn:example:>

SELECT ?personName WHERE {
  ?person :name ?personName.
  ?person :bornIn  / :within* / :name "United States".
  ?person :livesIn / :within* / :name "Europe".
}

PREFIX : <urn:example:>

SELECT ?personName WHERE {
  ?person :name ?personName.
  ?person :bornIn  / :within* / :name "United States".
  ?person :livesIn / :within* / :name "Europe".
}

(人) -[:BORN_IN]-> () -[:WITHIN*0..]-> (位置) # Cypher

？人：出生/：在* ？地点。#SPARQL

(person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (location)   # Cypher

?person :bornIn / :within* ?location.                   # SPARQL

(usa {name:'美国'}) # Cypher

?usa ：名称“美国”。#SPARQL

(usa {name:'United States'})   # Cypher

?usa :name "United States".    # SPARQL

基金会：数据记录

The Foundation: Datalog

Datalog是一种比 SPARQL 或 Cypher 更古老的语言 ，在20世纪 80 年代已被学者广泛研究 [ 44,45,46 ]。它在软件工程师中不太为人所知，但它仍然很重要，因为它为后来的查询语言构建提供了基础。

Datalog is a much older language than SPARQL or Cypher, having been studied extensively by academics in the 1980s [44, 45, 46]. It is less well known among software engineers, but it is nevertheless important, because it provides the foundation that later query languages build upon.

在实践中，Datalog被用在一些数据系统中：例如，它是Datomic[ 40 ] 的查询语言，而Cascalog[ 47 ]是在Hadoop中查询大型数据集的Datalog实现。^八

In practice, Datalog is used in a few data systems: for example, it is the query language of Datomic [40], and Cascalog [47] is a Datalog implementation for querying large datasets in Hadoop.^viii

Datalog的数据模型类似于三重存储模型，稍微概括一下。我们不将三元组写为（主语，谓语，宾语），而是将其写为谓语（主语，宾语）。 示例 2-10显示了如何将示例中的数据写入 Datalog。

Datalog’s data model is similar to the triple-store model, generalized a bit. Instead of writing a triple as (subject, predicate, object), we write it as predicate(subject, object). Example 2-10 shows how to write the data from our example in Datalog.

name(namerica, 'North America').
type(namerica, continent).

name(usa, 'United States').
type(usa, country).
within(usa, namerica).

name(idaho, 'Idaho').
type(idaho, state).
within(idaho, usa).

name(lucy, 'Lucy').
born_in(lucy, idaho).

name(namerica, 'North America').
type(namerica, continent).

name(usa, 'United States').
type(usa, country).
within(usa, namerica).

name(idaho, 'Idaho').
type(idaho, state).
within(idaho, usa).

name(lucy, 'Lucy').
born_in(lucy, idaho).

现在我们已经定义了数据，我们可以编写与之前相同的查询，如 示例 2-11所示。它看起来与 Cypher 或 SPARQL 中的等效项有点不同，但不要因此而失望。Datalog 是 Prolog 的子集，如果您学过计算机科学，您可能以前见过 Prolog。

Now that we have defined the data, we can write the same query as before, as shown in Example 2-11. It looks a bit different from the equivalent in Cypher or SPARQL, but don’t let that put you off. Datalog is a subset of Prolog, which you might have seen before if you’ve studied computer science.

within_recursive(Location, Name) :- name(Location, Name).     /* Rule 1 */

within_recursive(Location, Name) :- within(Location, Via),    /* Rule 2 */
                                    within_recursive(Via, Name).

migrated(Name, BornIn, LivingIn) :- name(Person, Name),       /* Rule 3 */
                                    born_in(Person, BornLoc),
                                    within_recursive(BornLoc, BornIn),
                                    lives_in(Person, LivingLoc),
                                    within_recursive(LivingLoc, LivingIn).

?- migrated(Who, 'United States', 'Europe').
/* Who = 'Lucy'. */

within_recursive(Location, Name) :- name(Location, Name).     /* Rule 1 */

within_recursive(Location, Name) :- within(Location, Via),    /* Rule 2 */
                                    within_recursive(Via, Name).

migrated(Name, BornIn, LivingIn) :- name(Person, Name),       /* Rule 3 */
                                    born_in(Person, BornLoc),
                                    within_recursive(BornLoc, BornIn),
                                    lives_in(Person, LivingLoc),
                                    within_recursive(LivingLoc, LivingIn).

?- migrated(Who, 'United States', 'Europe').
/* Who = 'Lucy'. */

Cypher 和 SPARQL 立即加入SELECT，但 Datalog 一次只迈一小步。我们定义告诉数据库新谓词的 规则within_recursive：在这里，我们定义两个新谓词和migrated。这些谓词不是存储在数据库中的三元组，而是从数据或其他规则派生的。规则可以引用其他规则，就像函数可以调用其他函数或递归调用自身一样。像这样，复杂的查询可以一次构建一小部分。

Cypher and SPARQL jump in right away with SELECT, but Datalog takes a small step at a time. We define rules that tell the database about new predicates: here, we define two new predicates, within_recursive and migrated. These predicates aren’t triples stored in the database, but instead they are derived from data or from other rules. Rules can refer to other rules, just like functions can call other functions or recursively call themselves. Like this, complex queries can be built up a small piece at a time.

在规则中，以大写字母开头的单词是变量，谓词的匹配类似于 Cypher 和 SPARQL。例如，name(Location, Name)将三元组 name(namerica, 'North America')与变量绑定 Location = namerica和进行匹配Name = 'North America'。

In rules, words that start with an uppercase letter are variables, and predicates are matched like in Cypher and SPARQL. For example, name(Location, Name) matches the triple name(namerica, 'North America') with variable bindings Location = namerica and Name = 'North America'.

如果系统可以找到运算符右侧 所有谓词的匹配项，则规则适用:-。当规则应用时，就好像 的左侧:-被添加到数据库中（变量被它们匹配的值替换）。

A rule applies if the system can find a match for all predicates on the righthand side of the :- operator. When the rule applies, it’s as though the lefthand side of the :- was added to the database (with variables replaced by the values they matched).

应用规则的一种可能的方式是：

One possible way of applying the rules is thus:

1. name(namerica, 'North America')存在于数据库中，因此规则 1 适用。它生成within_recursive(namerica, 'North America').

2. name(namerica, 'North America') exists in the database, so rule 1 applies. It generates within_recursive(namerica, 'North America').

3. within(usa, namerica)存在于数据库中且上一步生成 within_recursive(namerica, 'North America')，因此规则 2 适用。它生成 within_recursive(usa, 'North America').

4. within(usa, namerica) exists in the database and the previous step generated within_recursive(namerica, 'North America'), so rule 2 applies. It generates within_recursive(usa, 'North America').

5. within(idaho, usa)存在于数据库中且上一步生成 within_recursive(usa, 'North America')，因此规则 2 适用。它生成 within_recursive(idaho, 'North America').

6. within(idaho, usa) exists in the database and the previous step generated within_recursive(usa, 'North America'), so rule 2 applies. It generates within_recursive(idaho, 'North America').

通过重复应用规则 1 和 2，within_recursive谓词可以告诉我们数据库中包含的北美所有位置（或任何其他位置名称）。该过程如图2-6所示。

By repeated application of rules 1 and 2, the within_recursive predicate can tell us all the locations in North America (or any other location name) contained in our database. This process is illustrated in Figure 2-6.

图 2-6。使用示例 2-11中的数据记录规则确定爱达荷州位于北美。

现在规则 3 可以找到出生在某个地点BornIn并居住在某个地点 的人LivingIn。通过使用BornIn = 'United States'and 进行查询LivingIn = 'Europe'，并将 person 作为变量Who，我们要求 Datalog 系统找出该变量可以出现哪些值Who。因此，最终我们得到了与之前的 Cypher 和 SPARQL 查询相同的答案。

Now rule 3 can find people who were born in some location BornIn and live in some location LivingIn. By querying with BornIn = 'United States' and LivingIn = 'Europe', and leaving the person as a variable Who, we ask the Datalog system to find out which values can appear for the variable Who. So, finally we get the same answer as in the earlier Cypher and SPARQL queries.

Datalog 方法需要与本章讨论的其他查询语言不同的思维，但它是一种非常强大的方法，因为规则可以在不同的查询中组合和重用。对于简单的一次性查询来说不太方便，但如果数据很复杂，它可以更好地应对。

The Datalog approach requires a different kind of thinking to the other query languages discussed in this chapter, but it’s a very powerful approach, because rules can be combined and reused in different queries. It’s less convenient for simple one-off queries, but it can cope better if your data is complex.

哈希索引

Hash Indexes

让我们从键值数据的索引开始。这不是唯一可以索引的数据类型，但它很常见，并且是更复杂索引的有用构建块。

Let’s start with indexes for key-value data. This is not the only kind of data you can index, but it’s very common, and it’s a useful building block for more complex indexes.

键值存储与大多数编程语言中可以找到的字典类型非常相似，通常以哈希映射（哈希表）的形式实现。哈希图在许多算法教科书 [ 1 , 2 ]中都有描述，因此我们在这里不详细介绍它们的工作原理。既然我们已经有了内存数据结构的哈希映射，为什么不使用它们来索引磁盘上的数据呢？

Key-value stores are quite similar to the dictionary type that you can find in most programming languages, and which is usually implemented as a hash map (hash table). Hash maps are described in many algorithms textbooks [1, 2], so we won’t go into detail of how they work here. Since we already have hash maps for our in-memory data structures, why not use them to index our data on disk?

假设我们的数据存储仅包含附加到文件，如前面的示例所示。那么最简单的索引策略就是：在内存中保留一个哈希映射，其中每个键都映射到数据文件中的字节偏移量（可以找到该值的位置），如图 3-1所示。每当您将新的键值对附加到文件时，您还会更新哈希映射以反映刚刚写入的数据的偏移量（这既适用于插入新键，也适用于更新现有键）。当您想要查找某个值时，请使用哈希映射查找数据文件中的偏移量，查找该位置并读取该值。

Let’s say our data storage consists only of appending to a file, as in the preceding example. Then the simplest possible indexing strategy is this: keep an in-memory hash map where every key is mapped to a byte offset in the data file—the location at which the value can be found, as illustrated in Figure 3-1. Whenever you append a new key-value pair to the file, you also update the hash map to reflect the offset of the data you just wrote (this works both for inserting new keys and for updating existing keys). When you want to look up a value, use the hash map to find the offset in the data file, seek to that location, and read the value.

图 3-1。以类似 CSV 的格式存储键值对日志，并使用内存中的哈希映射进行索引。

这听起来可能很简单，但却是一个可行的方法。事实上，这本质上就是 Bitcask（Riak 中的默认存储引擎）所做的事情 [ 3 ]。Bitcask 提供高性能读取和写入，但要求所有密钥都适合可用 RAM，因为哈希映射完全保存在内存中。这些值可以使用比可用内存更多的空间，因为只需一次磁盘查找即可从磁盘加载它们。如果数据文件的该部分已经在文件系统缓存中，则读取根本不需要任何磁盘 I/O。

This may sound simplistic, but it is a viable approach. In fact, this is essentially what Bitcask (the default storage engine in Riak) does [3]. Bitcask offers high-performance reads and writes, subject to the requirement that all the keys fit in the available RAM, since the hash map is kept completely in memory. The values can use more space than there is available memory, since they can be loaded from disk with just one disk seek. If that part of the data file is already in the filesystem cache, a read doesn’t require any disk I/O at all.

像 Bitcask 这样的存储引擎非常适合每个键的值频繁更新的情况。例如，键可能是猫视频的 URL，值可能是播放次数（每次有人点击播放按钮时都会增加）。在这种工作负载中，有大量写入，但没有太多不同的键 - 每个键都有大量写入，但将所有键保留在内存中是可行的。

A storage engine like Bitcask is well suited to situations where the value for each key is updated frequently. For example, the key might be the URL of a cat video, and the value might be the number of times it has been played (incremented every time someone hits the play button). In this kind of workload, there are a lot of writes, but there are not too many distinct keys—you have a large number of writes per key, but it’s feasible to keep all keys in memory.

正如到目前为止所描述的，我们只追加到文件中，那么我们如何避免最终耗尽磁盘空间呢？一个好的解决方案是，通过在段文件达到一定大小时关闭该段文件，然后将后续写入写入新的段文件，将日志分成一定大小的段。然后我们可以对这些段进行压缩，如图3-2所示。压缩意味着丢弃日志中的重复键，并仅保留每个键的最新更新。

As described so far, we only ever append to a file—so how do we avoid eventually running out of disk space? A good solution is to break the log into segments of a certain size by closing a segment file when it reaches a certain size, and making subsequent writes to a new segment file. We can then perform compaction on these segments, as illustrated in Figure 3-2. Compaction means throwing away duplicate keys in the log, and keeping only the most recent update for each key.

图 3-2。压缩键值更新日志（计算每个猫视频的播放次数），仅保留每个键的最新值。

此外，由于压缩通常会使段变得更小（假设一个键在一个段内平均被覆盖多次），因此我们还可以在执行压缩的同时将多个段合并在一起，如图3-3所示。段在写入后就不会被修改，因此合并后的段将写入新文件。冻结段的合并和压缩可以在后台线程中完成，并且在进行过程中，我们仍然可以使用旧的段文件继续正常服务读写请求。合并过程完成后，我们将读取请求切换为使用新的合并段而不是旧段，然后可以简单地删除旧段文件。

Moreover, since compaction often makes segments much smaller (assuming that a key is overwritten several times on average within one segment), we can also merge several segments together at the same time as performing the compaction, as shown in Figure 3-3. Segments are never modified after they have been written, so the merged segment is written to a new file. The merging and compaction of frozen segments can be done in a background thread, and while it is going on, we can still continue to serve read and write requests as normal, using the old segment files. After the merging process is complete, we switch read requests to using the new merged segment instead of the old segments—and then the old segment files can simply be deleted.

图 3-3。同时执行压缩和段合并。

现在，每个段都有自己的内存中哈希表，将键映射到文件偏移量。为了找到键的值，我们首先检查最近段的哈希图；如果密钥不存在，我们将检查第二个最近的段，依此类推。合并过程使段数量保持较小，因此查找不需要检查许多哈希映射。

Each segment now has its own in-memory hash table, mapping keys to file offsets. In order to find the value for a key, we first check the most recent segment’s hash map; if the key is not present we check the second-most-recent segment, and so on. The merging process keeps the number of segments small, so lookups don’t need to check many hash maps.

要使这个简单的想法付诸实践需要很多细节。简而言之，实际实施中一些重要的问题是：

Lots of detail goes into making this simple idea work in practice. Briefly, some of the issues that are important in a real implementation are:

文件格式

File format

CSV 不是日志的最佳格式。使用二进制格式更快更简单，首先以字节为单位编码字符串的长度，然后是原始字符串（无需转义）。

CSV is not the best format for a log. It’s faster and simpler to use a binary format that first encodes the length of a string in bytes, followed by the raw string (without need for escaping).

删除记录

Deleting records

如果要删除某个键及其关联值，则必须将特殊的删除记录附加到数据文件（有时称为逻辑删除）。合并日志段时，逻辑删除会告诉合并过程丢弃已删除键的任何先前值。

If you want to delete a key and its associated value, you have to append a special deletion record to the data file (sometimes called a tombstone). When log segments are merged, the tombstone tells the merging process to discard any previous values for the deleted key.

崩溃恢复

Crash recovery

如果数据库重新启动，内存中的哈希映射将丢失。原则上，您可以通过从头到尾读取整个段文件并记下每个键的最新值的偏移量来恢复每个段的哈希映射。但是，如果段文件很大，这可能需要很长时间，这会使服务器重新启动变得痛苦。 Bitcask 通过在磁盘上存储每个段的哈希图的快照来加速恢复，可以更快地将其加载到内存中。

If the database is restarted, the in-memory hash maps are lost. In principle, you can restore each segment’s hash map by reading the entire segment file from beginning to end and noting the offset of the most recent value for every key as you go along. However, that might take a long time if the segment files are large, which would make server restarts painful. Bitcask speeds up recovery by storing a snapshot of each segment’s hash map on disk, which can be loaded into memory more quickly.

部分书面记录

Partially written records

数据库可能随时崩溃，包括在将记录追加到日志的过程中。Bitcask 文件包含校验和，允许检测并忽略日志中此类损坏的部分。

The database may crash at any time, including halfway through appending a record to the log. Bitcask files include checksums, allowing such corrupted parts of the log to be detected and ignored.

并发控制

Concurrency control

由于写入操作是按照严格的顺序附加到日志中的，因此一种常见的实现选择是只有一个写入器线程。数据文件段是仅追加的且不可变的，因此它们可以由多个线程同时读取。

As writes are appended to the log in a strictly sequential order, a common implementation choice is to have only one writer thread. Data file segments are append-only and otherwise immutable, so they can be read concurrently by multiple threads.

乍一看，仅附加日志似乎很浪费：为什么不就地更新文件，用新值覆盖旧值？但事实证明，仅附加设计是好的，原因如下：

An append-only log seems wasteful at first glance: why don’t you update the file in place, overwriting the old value with the new value? But an append-only design turns out to be good for several reasons:

• 追加和段合并是顺序写入操作，通常比随机写入快得多，特别是在磁旋转磁盘硬盘驱动器上。在某种程度上，顺序写入也更适合基于闪存的固态驱动器（SSD）[ 4 ]。我们将在“比较 B 树和 LSM 树”中进一步讨论这个问题。

• Appending and segment merging are sequential write operations, which are generally much faster than random writes, especially on magnetic spinning-disk hard drives. To some extent sequential writes are also preferable on flash-based solid state drives (SSDs) [4]. We will discuss this issue further in “Comparing B-Trees and LSM-Trees”.

• 如果段文件是仅追加的或不可变的，那么并发和崩溃恢复就会简单得多。例如，您不必担心在覆盖值时发生崩溃的情况，从而留下一个包含部分旧值和部分新值拼接在一起的文件。

• Concurrency and crash recovery are much simpler if segment files are append-only or immutable. For example, you don’t have to worry about the case where a crash happened while a value was being overwritten, leaving you with a file containing part of the old and part of the new value spliced together.

• 合并旧段可以避免数据文件随着时间的推移而变得碎片化的问题。

• Merging old segments avoids the problem of data files getting fragmented over time.

但是，哈希表索引也有局限性：

However, the hash table index also has limitations:

• 哈希表必须适合内存，因此如果您有大量键，那么您就不走运了。原则上，您可以在磁盘上维护哈希映射，但不幸的是很难使磁盘上的哈希映射表现良好。它需要大量的随机访问 I/O，当它变满时增长的成本很高，并且哈希冲突需要复杂的逻辑 [ 5 ]。

• The hash table must fit in memory, so if you have a very large number of keys, you’re out of luck. In principle, you could maintain a hash map on disk, but unfortunately it is difficult to make an on-disk hash map perform well. It requires a lot of random access I/O, it is expensive to grow when it becomes full, and hash collisions require fiddly logic [5].

• 范围查询效率不高。例如，您无法轻松扫描 和 之间的所有键kitty00000-kitty99999您必须在哈希映射中单独查找每个键。

• Range queries are not efficient. For example, you cannot easily scan over all keys between kitty00000 and kitty99999—you’d have to look up each key individually in the hash maps.

在下一节中，我们将研究没有这些限制的索引结构。

In the next section we will look at an indexing structure that doesn’t have those limitations.

SSTable 和 LSM 树

SSTables and LSM-Trees

在图3-3中，每个日志结构存储段都是一个键值对序列。这些对按照写入的顺序出现，日志中较后的值优先于日志中较早的相同键的值。除此之外，文件中键值对的顺序并不重要。

In Figure 3-3, each log-structured storage segment is a sequence of key-value pairs. These pairs appear in the order that they were written, and values later in the log take precedence over values for the same key earlier in the log. Apart from that, the order of key-value pairs in the file does not matter.

现在我们可以对段文件的格式进行简单的更改：我们要求键值对的序列按 key排序。乍一看，这个要求似乎破坏了我们使用顺序写入的能力，但我们稍后会讨论这个问题。

Now we can make a simple change to the format of our segment files: we require that the sequence of key-value pairs is sorted by key. At first glance, that requirement seems to break our ability to use sequential writes, but we’ll get to that in a moment.

我们将这种格式称为“排序字符串表”，简称SSTable 。我们还要求每个键在每个合并的段文件中仅出现一次（压缩过程已经确保了这一点）。与具有哈希索引的日志段相比，SSTable 具有几大优势：

We call this format Sorted String Table, or SSTable for short. We also require that each key only appears once within each merged segment file (the compaction process already ensures that). SSTables have several big advantages over log segments with hash indexes:

1. 即使文件大于可用内存，合并段也是简单而高效的。该方法类似于归并排序算法中使用的方法，如图 3-4所示 ：开始并排读取输入文件，查看每个文件中的第一个键，复制最低的键（根据排序顺序）到输出文件，然后重复。这会生成一个新的合并段文件，也按键排序。

   

   图 3-4。合并多个 SSTable 段，仅保留每个键的最新值。

   如果同一个键出现在多个输入段中怎么办？请记住，每个段都包含在某个时间段内写入数据库的所有值。这意味着一个输入段中的所有值必须比另一段中的所有值更新（假设我们始终合并相邻段）。当多个段包含相同的键时，我们可以保留最近段中的值并丢弃旧段中的值。

2. Merging segments is simple and efficient, even if the files are bigger than the available memory. The approach is like the one used in the mergesort algorithm and is illustrated in Figure 3-4: you start reading the input files side by side, look at the first key in each file, copy the lowest key (according to the sort order) to the output file, and repeat. This produces a new merged segment file, also sorted by key.

   Figure 3-4. Merging several SSTable segments, retaining only the most recent value for each key.

   What if the same key appears in several input segments? Remember that each segment contains all the values written to the database during some period of time. This means that all the values in one input segment must be more recent than all the values in the other segment (assuming that we always merge adjacent segments). When multiple segments contain the same key, we can keep the value from the most recent segment and discard the values in older segments.

3. 为了在文件中查找特定键，您不再需要在内存中保留所有键的索引。请参见图3-5的示例：假设您正在查找 key handiwork，但您不知道该 key 在段文件中的确切偏移量。然而，您确实知道“keys handbag ”和“handicraft”的偏移量，并且由于排序，您知道“ handiwork”必须出现在这两者之间。这意味着您可以跳转到手提包的偏移量并从那里开始扫描，直到找到手工品（或者如果密钥不存在于文件中，则找不到）。

   

   图 3-5。具有内存索引的 SSTable。

   您仍然需要一个内存中索引来告诉您某些键的偏移量，但它可以是稀疏的：每几千字节的段文件一个键就足够了，因为可以很快扫描几千字节。^我

4. In order to find a particular key in the file, you no longer need to keep an index of all the keys in memory. See Figure 3-5 for an example: say you’re looking for the key handiwork, but you don’t know the exact offset of that key in the segment file. However, you do know the offsets for the keys handbag and handsome, and because of the sorting you know that handiwork must appear between those two. This means you can jump to the offset for handbag and scan from there until you find handiwork (or not, if the key is not present in the file).

   Figure 3-5. An SSTable with an in-memory index.

   You still need an in-memory index to tell you the offsets for some of the keys, but it can be sparse: one key for every few kilobytes of segment file is sufficient, because a few kilobytes can be scanned very quickly.ⁱ

5. 由于读取请求无论如何都需要扫描请求范围内的多个键值对，因此可以将这些记录分组到一个块中并在将其写入磁盘之前进行压缩（如图 3-5 中的阴影区域所示）。然后，稀疏内存索引的每个条目都指向压缩块的开头。除了节省磁盘空间之外，压缩还可以减少 I/O 带宽的使用。

6. Since read requests need to scan over several key-value pairs in the requested range anyway, it is possible to group those records into a block and compress it before writing it to disk (indicated by the shaded area in Figure 3-5). Each entry of the sparse in-memory index then points at the start of a compressed block. Besides saving disk space, compression also reduces the I/O bandwidth use.

B树

B-Trees

到目前为止，我们讨论的日志结构索引正在获得认可，但它们并不是最常见的索引类型。最广泛使用的索引结构有很大不同：B 树。

The log-structured indexes we have discussed so far are gaining acceptance, but they are not the most common type of index. The most widely used indexing structure is quite different: the B-tree.

B 树 于 1970 年推出[ 17 ]，不到 10 年就被称为“无处不在”[ 18 ]，它很好地经受住了时间的考验。它们仍然是几乎所有关系数据库中的标准索引实现，许多非关系数据库也使用它们。

Introduced in 1970 [17] and called “ubiquitous” less than 10 years later [18], B-trees have stood the test of time very well. They remain the standard index implementation in almost all relational databases, and many nonrelational databases use them too.

与 SSTable 一样，B 树保持按键排序的键值对，这允许高效的键值查找和范围查询。但相似之处仅此而已：B 树具有非常不同的设计理念。

Like SSTables, B-trees keep key-value pairs sorted by key, which allows efficient key-value lookups and range queries. But that’s where the similarity ends: B-trees have a very different design philosophy.

我们之前看到的日志结构索引将数据库分解为可变大小的段，通常大小为几兆或更大，并且总是按顺序写入段。相比之下，B 树将数据库分解为固定大小的块或页，通常大小为 4 KB（有时更大），并且一次读取或写入一页。这种设计更符合底层硬件，因为磁盘也排列在固定大小的块中。

The log-structured indexes we saw earlier break the database down into variable-size segments, typically several megabytes or more in size, and always write a segment sequentially. By contrast, B-trees break the database down into fixed-size blocks or pages, traditionally 4 KB in size (sometimes bigger), and read or write one page at a time. This design corresponds more closely to the underlying hardware, as disks are also arranged in fixed-size blocks.

每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面——类似于指针，但在磁盘上而不是在内存中。我们可以使用这些页面引用来构建页面树，如图3-6所示。

Each page can be identified using an address or location, which allows one page to refer to another—similar to a pointer, but on disk instead of in memory. We can use these page references to construct a tree of pages, as illustrated in Figure 3-6.

图 3-6。使用 B 树索引查找键。

将一页指定为B 树的根；每当您想在索引中查找某个键时，都可以从这里开始。该页面包含多个键和对子页面的引用。每个子项负责一个连续的键范围，并且引用之间的键指示这些范围之间的边界所在。

One page is designated as the root of the B-tree; whenever you want to look up a key in the index, you start here. The page contains several keys and references to child pages. Each child is responsible for a continuous range of keys, and the keys between the references indicate where the boundaries between those ranges lie.

在图 3-6的示例中，我们正在寻找键 251，因此我们知道我们需要遵循边界 200 和 300 之间的页面引用。这将我们带到一个外观相似的页面，该页面进一步分解了 200 –300 个范围划分为子范围。最终我们到达包含各个键的页面（叶页面），该页面要么包含每个内联键的值，要么包含对可以找到这些值的页面的引用。

In the example in Figure 3-6, we are looking for the key 251, so we know that we need to follow the page reference between the boundaries 200 and 300. That takes us to a similar-looking page that further breaks down the 200–300 range into subranges. Eventually we get down to a page containing individual keys (a leaf page), which either contains the value for each key inline or contains references to the pages where the values can be found.

B 树一页中对子页的引用数量称为分支因子。例如，在图 3-6中，分支因子为 6。实际上，分支因子取决于存储页面引用和范围边界所需的空间量，但通常为数百。

The number of references to child pages in one page of the B-tree is called the branching factor. For example, in Figure 3-6 the branching factor is six. In practice, the branching factor depends on the amount of space required to store the page references and the range boundaries, but typically it is several hundred.

如果要更新 B 树中现有键的值，请搜索包含该键的叶页，更改该页中的值，然后将该页写回磁盘（对该页的任何引用仍然有效） 。如果要添加新键，则需要找到范围包含新键的页面并将其添加到该页面。如果页面中没有足够的可用空间来容纳新键，则会将其分为两个半满页面，并更新父页面以适应键范围的新细分 - 请参见图 3-7。^二、

If you want to update the value for an existing key in a B-tree, you search for the leaf page containing that key, change the value in that page, and write the page back to disk (any references to that page remain valid). If you want to add a new key, you need to find the page whose range encompasses the new key and add it to that page. If there isn’t enough free space in the page to accommodate the new key, it is split into two half-full pages, and the parent page is updated to account for the new subdivision of key ranges—see Figure 3-7.ⁱⁱ

图 3-7。通过拆分页面来增长 B 树。

该算法确保树保持平衡：具有n 个键的 B 树的深度始终为O (log  n )。大多数数据库都可以放入三层或四层深度的 B 树中，因此您无需遵循许多页面引用即可找到您要查找的页面。（分支因子为 500 的 4 KB 页面的四级树最多可存储 256 TB。）

This algorithm ensures that the tree remains balanced: a B-tree with n keys always has a depth of O(log n). Most databases can fit into a B-tree that is three or four levels deep, so you don’t need to follow many page references to find the page you are looking for. (A four-level tree of 4 KB pages with a branching factor of 500 can store up to 256 TB.)